线段树合并洛谷题单链接点这里

CF1009F Dominant Indices

权值线段树动态开点的时候，如果merge是开新点的话就会爆空间如果不是开新点的话有时候出题人想卡你就会wa掉
n=1e6的时候要特别小心，大多数处理不好的话是会MLE的
下面有位大佬提出了解决思路

未优化版本代码

#include
using namespace std;
const int N=1e6+10,M=2*N;
int h[N],ne[M],e[M],idx,o,dep[N],sz[N];
int root[N*22],ls[N*22],rs[N*22],n,m;
int sum[N*22],ans[N*22];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void pushup(int u){
    if(sum[ls[u]]>=sum[rs[u]]){
        sum[u]=sum[ls[u]];
        ans[u]=ans[ls[u]];
    }
    else{
        sum[u]=sum[rs[u]];
        ans[u]=ans[rs[u]];
    }
}
void dfs1(int u,int fa=0){
    dep[u]=dep[fa]+1;
    sz[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        dfs1(j,u);
        sz[u]+=sz[j];
    }
}
void modify(int &u,int l,int r,int x,int k=1){
    if(!u)u=++o;
    if(l==r){
        sum[u]+=k;
        ans[u]=x;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls[u],l,mid,x,k);
    else modify(rs[u],mid+1,r,x,k);
    pushup(u);
}
// int merge(int a,int b,int l,int r){
//     if(!a||!b)return a|b;
//     int x=++o;
//     if(l==r){
        
//         sum[x]=sum[a]+sum[b];
//         ans[x]=min(ans[a],ans[b]);
//         return x;
//     }
//     int mid=l+r>>1;
//     ls[x]=merge(ls[a],ls[b],l,mid);
//     rs[x]=merge(rs[a],rs[b],mid+1,r);
//     pushup(x);
//     return x;
// }
int merge(int a,int b,int l,int r){
    if(!a||!b)return a|b;
    if(l==r){
        sum[a]+=sum[b];
        ans[a]=min(ans[a],ans[b]);
        return a;
    }
    int mid=l+r>>1;
    ls[a]=merge(ls[a],ls[b],l,mid);
    rs[a]=merge(rs[a],rs[b],mid+1,r);
    pushup(a);
    return a;
}
void dfs2(int u,int fa=0){
    modify(root[u],1,n,dep[u],1);
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        dfs2(j,u);
        root[u]=merge(root[u],root[j],1,n);
    }
}

int a,b,k;
signed main(){
    memset(h,-1,sizeof h);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs1(1);
    dfs2(1);
    for(int i=1;i<=n;i++)cout<<ans[root[i]]-dep[i]<<'\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

优化版本代码

#include
using namespace std;
const int N=2e6+10,M=2*N;
int h[N],ne[M],e[M],idx,o,dep[N],sz[N];
int root[N],ls[N],rs[N],n,m;
int sum[N],ans[N];
int st[N*2],top;
int newnode(){
    if(top)return st[top--];
    return ++o;
}
void clear(int x){
    sum[x]=0;
    // ans[x]=0;
    ls[x]=0;
    rs[x]=0;
}
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void pushup(int u){
    if(sum[ls[u]]>=sum[rs[u]]){
        sum[u]=sum[ls[u]];
        ans[u]=ans[ls[u]];
    }
    else{
        sum[u]=sum[rs[u]];
        ans[u]=ans[rs[u]];
    }
}
void dfs1(int u,int fa=0){
    dep[u]=dep[fa]+1;
    sz[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        dfs1(j,u);
        sz[u]+=sz[j];
    }
}
void modify(int &u,int l,int r,int x,int k=1){
    if(!u)u=newnode();
    if(l==r){
        sum[u]+=k;
        ans[u]=x;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls[u],l,mid,x,k);
    else modify(rs[u],mid+1,r,x,k);
    pushup(u);
}
int merge(int a,int b,int l,int r){
    if(!a||!b)return a|b;
    if(l==r){
        sum[a]+=sum[b];
        ans[a]=min(ans[a],ans[b]);
        st[++top]=b,clear(b);
        return a;
    }
    int mid=l+r>>1;
    ls[a]=merge(ls[a],ls[b],l,mid);
    rs[a]=merge(rs[a],rs[b],mid+1,r);
    pushup(a);
    st[++top]=b,clear(b);
    return a;
}
int res[N];
void dfs2(int u,int fa=0){
    
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        dfs2(j,u);
        root[u]=merge(root[u],root[j],1,n);
    }modify(root[u],1,n,dep[u],1);
    res[u]=ans[root[u]]-dep[u];
}

int a,b,k;
signed main(){
    memset(h,-1,sizeof h);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs1(1);
    dfs2(1);
    for(int i=1;i<=n;i++)cout<<res[i]<<'\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

---

CF570D Tree Requests

错误的在线做法，不知道错哪了

#include
using namespace std;
const int N=2e6+10,M=N;
int h[N],e[M],ne[M],idx,o,dep[N],w[N];
int ls[N],rs[N],cnt[N],n,m,root[N];
struct node{
    int i,a,b;
};
vector<node>q[N];
int st[N],top;
int newnode(){
    if(top)return st[top--];
    return ++o;
}
void clear(int x){
    ls[x]=rs[x]=cnt[x]=0;
}
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void pushup(int u){
    cnt[u]=cnt[ls[u]]^cnt[rs[u]];
}
void modify(int &u,int l,int r,int x,int k){
    if(!u)u=newnode();
    if(l==r){
        cnt[u]^=k;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls[u],l,mid,x,k);
    else modify(rs[u],mid+1,r,x,k);
    pushup(u);
}
int merge(int a,int b,int l,int r){
    if(!a||!b)return a|b;
    int x=newnode();
    if(l==r){
        cnt[x]=cnt[a]^cnt[b];
        //st[++top]=b,clear(b);
        return x;
    }
    int mid=l+r>>1;
    ls[x]=merge(ls[a],ls[b],1,mid);
    rs[x]=merge(rs[a],rs[b],mid+1,r);
    pushup(x);
    //st[++top]=b,clear(b);
    return x;
}
void dfs1(int u,int fa=0){
    dep[u]=dep[fa]+1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs1(j,u);
    }
}
int ans[N];
int query(int u,int l,int r,int x){
    if(!u)return 0;
    if(l==r)return cnt[u];
    int mid=l+r>>1;
    if(x<=mid)return query(ls[u],l,mid,x);
    else return query(rs[u],mid+1,r,x);
}
void dfs2(int u,int fa=0){
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs2(j);
        root[u]=merge(root[u],root[j],1,n);
    }
    modify(root[u],1,n,dep[u],1<<w[u]);
    return;
    for(auto t:q[u]){
        int i=t.i;
        int b=t.b;
        if(b>n){ans[i]=0;continue;}
        
        int j=query(root[u],1,n,b);
        //cout<<"j="<
        if(j==(j&-j))ans[i]=1;
        else ans[i]=0;
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    memset(h,-1,sizeof h);
    cin>>n>>m;
    // for(int i=1;i<=m;i++)ans[i]=1;
    for(int i=2;i<=n;i++){
        int x;
        cin>>x;
        add(x,i);
    }
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        w[i]=c-'a';
    }
    dfs1(1);
    dfs2(1);
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        // q[a].push_back({i,a,b});
        // continue;
        int t=query(root[a],1,n,b);
        if(b>n||t==(t&-t))cout<<"Yes"<<'\n';
        else cout<<"No"<<'\n';
    }
    
    // for(int i=1;i<=m;i++){
    //     if(ans[i])cout<<"Yes"<<'\n';
    //     else cout<<"No"<<'\n';
    // }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

离线

#include
using namespace std;
const int N=5e5+10,M=N;
int h[N],e[M],ne[M],idx,o,dep[N],w[N];
int ls[N*20],rs[N*20],cnt[N*20],n,m,root[N*20];
struct node{
    int i,a,b;
};
vector<node>q[N];
int st[N],top;
int newnode(){
    if(top)return st[top--];
    return ++o;
}
void clear(int x){
    ls[x]=rs[x]=cnt[x]=0;
}
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void pushup(int u){
    cnt[u]=cnt[ls[u]]^cnt[rs[u]];
}
void modify(int &u,int l,int r,int x,int k){
    if(!u)u=newnode();
    if(l==r){
        cnt[u]^=k;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls[u],l,mid,x,k);
    else modify(rs[u],mid+1,r,x,k);
    pushup(u);
}
// int merge(int a,int b,int l,int r){
//     if(!a||!b)return a|b;
//     int x=newnode();
//     if(l==r){
//         cnt[x]=cnt[a]^cnt[b];
//         // cnt[a]^=cnt[b];
//         st[++top]=b,clear(b);
//         st[++top]=a,clear(a);
//         return x;
//     }
//     int mid=l+r>>1;
//     ls[x]=merge(ls[a],ls[b],1,mid);
//     rs[x]=merge(rs[a],rs[b],mid+1,r);
//     pushup(x);
//     st[++top]=b,clear(b);
//     st[++top]=a,clear(a);
//     return x;
// }
int merge(int a,int b,int l,int r){
    if(!a||!b)return a|b;
    if(l==r){
        cnt[a]^=cnt[b];
        return a;
    }
    int mid=l+r>>1;
    ls[a]=merge(ls[a],ls[b],l,mid);
    rs[a]=merge(rs[a],rs[b],mid+1,r);
    pushup(a);
    return a;
}
void dfs1(int u,int fa=0){
    dep[u]=dep[fa]+1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs1(j,u);
    }
}
int ans[N];
int query(int u,int l,int r,int x){
    if(!u)return 0;
    if(l==r)return cnt[u];
    int mid=l+r>>1;
    if(x<=mid)return query(ls[u],l,mid,x);
    else return query(rs[u],mid+1,r,x);
}
void dfs2(int u,int fa=0){
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs2(j);
        root[u]=merge(root[u],root[j],1,n);
    }
    modify(root[u],1,n,dep[u],1<<w[u]);
    for(auto t:q[u]){
        int i=t.i;
        int b=t.b;
        if(b>n){ans[i]=1;continue;}
        int j=query(root[u],1,n,b);
        if(j==(j&-j))ans[i]=1;
        else ans[i]=0;
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    memset(h,-1,sizeof h);
    cin>>n>>m;
    // for(int i=1;i<=m;i++)ans[i]=1;
    for(int i=2;i<=n;i++){
        int x;
        cin>>x;
        add(x,i);
    }
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        w[i]=c-'a';
    }
    dfs1(1);
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        q[a].push_back({i,a,b});
    }
    dfs2(1);
    for(int i=1;i<=m;i++){
        if(ans[i])cout<<"Yes"<<'\n';
        else cout<<"No"<<'\n';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

---

dfs序+bfs序的前缀和

#include  

using namespace std;
const int N=5e5+10;
int h[N],e[N],ne[N],idx,o;
int w[N],n,m,dep[N],dfn[N],ed[N],dot[N];
vector<int>v[N],a[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int maxdep;
void dfs(int u,int fa=0){
    dep[u]=dep[fa]+1;
    maxdep=max(maxdep,dep[u]);
    dfn[u]=++o;
    v[dep[u]].push_back(o);
    dot[o]=u;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs(j,u);
    }
    ed[u]=o;
}
signed main(){
    memset(h,-1,sizeof h);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=2;i<=n;i++){
        int x;
        cin>>x;
        add(x,i);
    }
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        w[i]=c-'a';
    }
    dfs(1);
    for(int i=1;i<=maxdep;i++){
        int k=dot[v[i][0]];
        a[i].push_back(1<<w[k]);
        for(int j=1;j<v[i].size();j++){
            k=dot[v[i][j]];
            // a[i][j]=a[i][j-1]^(1<
            a[i].push_back( a[i][j-1]^(1<<w[k]) );
        }
    }
    while(m--){
        int u,d;
        cin>>u>>d;
        int l=lower_bound(v[d].begin(),v[d].end(),dfn[u])-v[d].begin();
        int r=lower_bound(v[d].begin(),v[d].end(),ed[u]+1)-v[d].begin()-1;
        if(r<0){
            cout<<"Yes"<<'\n';
            continue;
        }
        int t;
        if(l==0)t=a[d][r];
        else t=a[d][r]^a[d][l-1];
        if(t==(t&-t))cout<<"Yes"<<'\n';
        else cout<<"No"<<'\n';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

CF246E Blood Cousins Return

#include
using namespace std;
const int N=2e5+10,M=N;
int h[N],e[M],ne[M],idx,o,dep[N],n,m,name,ans[N],w[N];
int root[N*20],ls[N*20],rs[N*20],sum[N*20];
set<int>s[N*20];
unordered_map<string,int>mp;
struct node{
    int i,k;
};
vector<node>q[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void modify(int &u,int l,int r,int x,int k){
    if(!u)u=++o;
    if(l==r){
        s[u].insert(k);
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls[u],l,mid,x,k);
    else modify(rs[u],mid+1,r,x,k);
}
int merge(int a,int b,int l=1,int r=n){
    if(!a||!b)return a|b;
    if(l==r){
        if(s[a].size()<s[b].size())swap(a,b);
        for(auto i:s[b])s[a].insert(i);
        return a;
    }
    int mid=l+r>>1;
    ls[a]=merge(ls[a],ls[b],l,mid);
    rs[a]=merge(rs[a],rs[b],mid+1,r);
    return a;
}
int query(int u,int l,int r,int x){
    if(!u)return 0;
    if(l==r)return s[u].size();
    int mid=l+r>>1;
    if(x<=mid)return query(ls[u],l,mid,x);
    return query(rs[u],mid+1,r,x);
}
void dfs(int u,int fa=0){
    dep[u]=dep[fa]+1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs(j,u);
        root[u]=merge(root[u],root[j]);
    }
    modify(root[u],1,n,dep[u],w[u]);
    for(auto t:q[u]){
        int i=t.i;
        int k=t.k;
        if(dep[u]+k>n)ans[i]=0;
        else
        ans[i]=query(root[u],1,n,dep[u]+k);
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    memset(h, -1, sizeof h);
    cin>>n;
    for(int i=1;i<=n;i++){
        string x;
        int fa;
        cin>>x>>fa;
        if(!mp.count(x))mp[x]=++name;
        w[i]=mp[x];
        add(fa,i);
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        int a,d;
        cin>>a>>d;
        q[a].push_back({i,d});
    }
    dep[0]=-1;
    dfs(0);
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

---

P3899 [湖南集训]更为厉害

#include
using namespace std;
const int N=3e5+10,M=2*N;
int h[N],ne[M],e[M],idx,o,dep[N],sz[N];
int root[N*40],ls[N*40],rs[N*40],n,m;
long long sum[N*40];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void pushup(int u){
    sum[u]=sum[ls[u]]+sum[rs[u]];
}
void dfs1(int u,int fa=0){
    dep[u]=dep[fa]+1;
    sz[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        dfs1(j,u);
        sz[u]+=sz[j];
    }
}
void modify(int &u,int l,int r,int x,int k){
    if(!u)u=++o;
    if(l==r){
        sum[u]+=k;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls[u],l,mid,x,k);
    else modify(rs[u],mid+1,r,x,k);
    pushup(u);
}
int merge(int a,int b,int l,int r){
    if(!a||!b)return a|b;
    int x=++o;
    if(l==r){
        // sum[a]+=sum[b];
        // return a;
        
        sum[x]=sum[a]+sum[b];
        return x;
    }
    int mid=l+r>>1;
    ls[x]=merge(ls[a],ls[b],l,mid);
    rs[x]=merge(rs[a],rs[b],mid+1,r);
    pushup(x);
    return x;
}
void dfs2(int u,int fa=0){
    modify(root[u],1,n,dep[u],sz[u]-1);
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        dfs2(j,u);
        root[u]=merge(root[u],root[j],1,n);
    }
}
long long query(int u,int ql,int qr,int l=1,int r=n){
    if(!u||l>r)return 0;
    if(l>qr||r<ql)return 0;
    if(ql<=l&&r<=qr)return sum[u];
    int mid=l+r>>1;
    long long t=0;
    if(mid>=l)t+=query(ls[u],ql,qr,l,mid);
    if(mid<r)t+=query(rs[u],ql,qr,mid+1,r);
    return t;
    return query(ls[u],ql,qr,l,mid)+query(rs[u],ql,qr,mid+1,r);
}
int a,b,k;
signed main(){
    memset(h,-1,sizeof h);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=2;i<=n;i++){
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs1(1);
    dfs2(1);
    while(m--){
        cin>>a>>k;
        long long ans1=(long long)(sz[a]-1)*min(dep[a]-1,k);
        long long ans2=query(root[a],dep[a]+1,dep[a]+k);
        cout<<ans1+ans2<<'\n';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

P5384 [Cnoi2019]雪松果树

下一道题的卡常版，主要是卡空间一直MLE

40分

#include
using namespace std;
const int N=2e6+10;
int n,m,h[N],e[N],ne[N],idx,f[N][21],dep[N];
int root[N],ls[N],rs[N],v[N],o;
int ans[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs1(int u){
    dep[u]=dep[f[u][0]]+1;
    for(int i=1;i<=20;i++)f[u][i]=f[f[u][i-1]][i-1];
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs1(j);
    }
}

int getk(int x,int k){
    for(int i=20;i>=0;i--){
        if(k>=(1<<i))k-=(1<<i),x=f[x][i];
    }
    return x;
}
void pushup(int u){
    v[u]=v[ls[u]]+v[rs[u]];
}
void modify(int &u,int l,int r,int x,int k){
    if(!u)u=++o;
    if(l==r){
        v[u]+=k;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls[u],l,mid,x,k);
    else modify(rs[u],mid+1,r,x,k);
    pushup(u);
}
int merge(int a,int b,int l,int r){
    if(!a||!b)return a|b;
    if(l==r){
        v[a]+=v[b];
        return a;
    }
    int mid=l+r>>1;
    ls[a]=merge(ls[a],ls[b],l,mid);
    rs[a]=merge(rs[a],rs[b],mid+1,r);
    pushup(a);
    return a;
}
typedef pair<int,int>Q;
#define i first
#define a second
vector<Q>q[N];
int cal(int u,int l,int r,int x){
    if(!u)return 0;
    if(l==r)return v[u];
    int mid=l+r>>1;
    if(x<=mid)return cal(ls[u],l,mid,x);
    else return cal(rs[u],mid+1,r,x);
}
void dfs2(int u){
    modify(root[u],1,n,dep[u],1);
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs2(j);
        root[u]=merge(root[u],root[j],1,n);
    }
    for(auto t:q[u]){
        int i=t.i;
        int a=t.a;
        ans[i]=cal(root[u],1,n,dep[a])-1;
    }
}


signed main(){
    memset(h,-1,sizeof h);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=2;i<=n;i++){
        cin>>f[i][0];
        add(f[i][0],i);
    }
    dfs1(1);
    
    for(int i=1;i<=m;i++){
        int u,k;
        cin>>u>>k;
        int fa=getk(u,k);
        q[fa].push_back({i,u});
    }
    dfs2(1);
    for(int i=1;i<=m;i++)cout<<ans[i]<<" ";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

80分

#include
using namespace std;
const int N=1e6+10;
int h[N],e[N],ne[N],idx,dep[N];
int o,dfn[N],dot[N],ed[N],f[N][15];
int n,m;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs1(int u){
    dfn[u]=++o;
    dot[dfn[u]]=u;
    dep[u]=dep[f[u][0]]+1;
    for(int i=1;i<=14;i++)f[u][i]=f[f[u][i-1]][i-1];
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs1(j);
    }
    ed[u]=o;
}
int getk(int x,int k){
    for(int i=14;i>=0;i--){
        if(k>=(1<<i))k-=(1<<i),x=f[x][i];
    }
    return x;
}
vector<int>v[N];
signed main(){
    memset(h,-1,sizeof h);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=2;i<=n;i++){
        cin>>f[i][0];
        add(f[i][0],i);
    }
    dfs1(1);
    //枚举的i是dfs序，按照递增dfs序插入一层层的深度
    for(int i=1;i<=n;i++)v[dep[dot[i]]].push_back(i);
    while(m--){
        int u,k;
        cin>>u>>k;
        int fa=getk(u,k);
        if(fa==0){cout<<0<<" ";continue;}
        else{
            int p=dep[u];
            int l=dfn[fa];
            int r=ed[fa];
            /*
            我是爸爸，我的儿子(dfs序)有1 2 3 4 5 6 7
            深度为p的儿子有2 5 7
            故我的kth同辈有3-1=2个
            */
            auto x=lower_bound(v[p].begin(),v[p].end(),l);
            auto y=lower_bound(v[p].begin(),v[p].end(),r+1);//r=7也有可能会用到
            cout<<y-x-1<<" ";
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

CF208E Blood Cousins

#include
using namespace std;
const int N=1e5+10;
int h[N],e[N],ne[N],idx,n,m;
int r,root[N*40],ls[N*40],rs[N*40],o,v[N*40];
int f[N][20],dep[N],ans[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs1(int u){
    dep[u]=dep[f[u][0]]+1;
    for(int i=1;i<20;i++)f[u][i]=f[f[u][i-1]][i-1];
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs1(j);
    }
}
void pushup(int u){
    v[u]=v[ls[u]]+v[rs[u]];
}
void modify(int &u,int l,int r,int x,int k){
    if(!u)u=++o;
    if(l==r){
        v[u]+=k;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls[u],l,mid,x,k);
    else modify(rs[u],mid+1,r,x,k);
    pushup(u);
}
int merge(int a,int b,int l,int r){
    if(!a||!b)return a|b;
    if(l==r){
        v[a]+=v[b];
        return a;
    }
    int mid=l+r>>1;
    ls[a]=merge(ls[a],ls[b],l,mid);
    rs[a]=merge(rs[a],rs[b],mid+1,r);
    pushup(a);
    return a;
}
int cal(int u,int l,int r,int x){
    if(!u)return 0;
    if(l==r)return v[u];
    int mid=l+r>>1;
    if(x<=mid)return cal(ls[u],l,mid,x);
    else return cal(rs[u],mid+1,r,x);
}
int getk(int x,int k){
    if(k==0)return x;
    int t=log2(k);
    return getk(f[x][t],k-(1<<t));
}
int getk2(int x,int k){
    for(int i=19;i>=0;i--){
        if(k>=(1<<i))k-=(1<<i),x=f[x][i];
    }
    return x;
}
struct Q{
    int i,a;
};
vector<Q>q[N];
void dfs2(int u){
    modify(root[u],1,n,dep[u],1);
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs2(j);
        root[u]=merge(root[u],root[j],1,n);
    }
    for(auto t:q[u]){//u现在是fa
        int i=t.i;
        int a=t.a;
        ans[i]=max(0,cal(root[u],1,n,dep[a])-1);
    }
    
}

signed main(){
    memset(h,-1,sizeof h);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>f[i][0];
        if(f[i][0])add(f[i][0],i);
    }
    for(int i=1;i<=n;i++){
        if(f[i][0]==0)dfs1(i);
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        int a,p;
        cin>>a>>p;
        int fa=getk2(a,p);
        q[fa].push_back({i,a});
    }
    for(int i=1;i<=n;i++){
        if(f[i][0]==0)dfs2(i);
    }
    
    for(int i=1;i<=m;i++)cout<<ans[i]<<" ";
    // while(m--){
    //     int a,p;
    //     cin>>a>>p;
    //     //p--;
    //     int fa=getk2(a,p);
    //     if(fa==0){
    //         cout<<0<<" ";
    //         continue;
    //     }
    //     int ans=cal(root[fa],1,n,dep[a]);
    //     //cout<
    //     cout<
    // }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

P3605 [USACO17JAN]Promotion Counting P

#include
using namespace std;
const int N=1e5+10;
int h[N],e[N],ne[N],idx;
int n,o,root[N*40],ls[N*40],rs[N*40],a[N],v[N*40];
int ans[N];
int m;
vector<int>xs;
int get(int x){
    return lower_bound(xs.begin(),xs.end(),x)-xs.begin()+1;
}
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void pushup(int u){
    v[u]=v[ls[u]]+v[rs[u]];
}
void modify(int &u,int l,int r,int x,int k){
    if(!u)u=++o;
    if(l==r){
        v[u]+=k;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls[u],l,mid,x,k);
    else modify(rs[u],mid+1,r,x,k);
    pushup(u);
    return;
}
int cal(int u,int l,int r,int x){//在u这棵树里权值小于等于x的有多少个
    if(!u)return 0;
    if(x>=r)return v[u];
    if(x<l)return 0;
    int mid=l+r>>1;
    if(x<=mid)return cal(ls[u],l,mid,x);
    return v[ls[u]]+cal(rs[u],mid+1,r,x);
}
int merge(int a,int b,int l,int r){
    if(!a||!b)return a|b;
    if(l==r){
        v[a]+=v[b];
        return a;
    }
    int mid=l+r>>1;
    ls[a]=merge(ls[a],ls[b],l,mid);
    rs[a]=merge(rs[a],rs[b],mid+1,r);
    pushup(a);
    return a;
}
int queryk(int u,int k,int l=1,int r=m){
    if(k>v[u])return 0;
    if(l==r)return k;
    int mid=l+r>>1;
    if(k<=v[ls[u]])return queryk(ls[u],k,l,mid);
    return queryk(rs[u],k-v[ls[u]],mid+1,r);
}
void dfs(int u){
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs(j);
        root[u]=merge(root[u],root[j],1,m);
    }
    int t=get(a[u]);
    // int l=1,r=n;
    // while(l
    //     int mid=l+r>>1;
    //     if(queryk(root[u],mid)<=t)r=mid;
    //     else l=mid+1;
    // }
    // if(queryk(root[u],r)==t)ans[u]=r;
    modify(root[u],1,m,get(a[u]),1);
    ans[u]=cal(root[u],1,m,get(1e9+1))-cal(root[u],1,m,get(a[u]));
    
}
signed main(){
    memset(h,-1,sizeof h);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        xs.push_back(a[i]);//问题转化为有多少个儿子权值比我大，第k大-1
    }
    xs.push_back(1e9+1);
    sort(xs.begin(),xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    m=xs.size();
    for(int i=2;i<=n;i++){
        int f;
        cin>>f;
        add(f,i);
    }
    dfs(1);
    for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

[POI2011]ROT-Tree Rotations

#include
using namespace std;
long long ans,ans1,ans2;
const int N=1e5+10;
int n,root[N*40],v[N*40],ls[N*40],rs[N*40],o;
void pushup(int u){
    v[u]=v[ls[u]]+v[rs[u]];
}
void modify(int &u,int l,int r,int x,int k=1){
    if(!u)u=++o;
    if(l==r){
        v[u]+=k;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls[u],l,mid,x,k);
    else modify(rs[u],mid+1,r,x,k);
    pushup(u);
}
int merge(int a,int b,int l,int r){
    if(!a||!b)return a|b;
    if(l==r){
        v[a]+=v[b];
        return a;
    }
    ans1+=(long long)v[ls[a]]*v[rs[b]];
    ans2+=(long long)v[rs[a]]*v[ls[b]];
    int mid=l+r>>1;
    ls[a]=merge(ls[a],ls[b],l,mid);
    rs[a]=merge(rs[a],rs[b],mid+1,r);
    pushup(a);
    return a;
}
void dfs(int &u){
    u=0;
    int t;
    int ls=0,rs=0;
    cin>>t;
    if(t)modify(u,1,n,t,1);
    else{
        
        dfs(ls),dfs(rs);
        ans1=ans2=0;
        u=merge(ls,rs,1,n);
        ans+=min(ans1,ans2);
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    //这道题因为是确切的n个叶子节点而且每个叶子节点不同
    //所以这个n有用，也就是说值域为1~n
    //但是也可能叶子节点权值可能相同
    int _=0;
    dfs(_);
    cout<<ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

永无乡

#include
using namespace std;
const int N=1e5+10;
int n,m,p[N],a[N*50],ls[N*50],rs[N*50],root[N*50],o;
int id[N];
int find(int x){
    if(p[x]==x)return x;
    return p[x]=find(p[x]);
}
void pushup(int u){
    a[u]=a[ls[u]]+a[rs[u]];
}
void modify(int &u,int l,int r,int x,int k){
    if(!u)u=++o;
    if(l==r){
        a[u]+=k;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls[u],l,mid,x,k);
    else modify(rs[u],mid+1,r,x,k);
    pushup(u);
}
int merge(int x,int y,int l,int r){
    if(!x||!y)return x|y;
    if(l==r){
        a[x]+=a[y];
        return x;
    }
    int mid=l+r>>1;
    ls[x]=merge(ls[x],ls[y],l,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,r);
    pushup(x);
    return x;
}
int queryk(int u,int l,int r,int k){
    if(k>a[u])return 0;
    if(l==r)return l;
    int mid=l+r>>1;
    if(k<=a[ls[u]])return queryk(ls[u],l,mid,k);
    else return queryk(rs[u],mid+1,r,k-a[ls[u]]);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        p[i]=i;
        int x;
        cin>>x;
        //每座岛都有自己的独一无二的重要度
        id[x]=i;//重要度为x的岛屿编号为i
        //如果每座岛重要度有可能重合选编号最大怎么办？
        //答案是按照要求sort一遍用下标代替独一无二的重要度
        modify(root[i],1,n,x,1);
    }
    id[0]=-1;
    while(m--){
        int x,y;
        cin>>x>>y;
        int fx=find(x);
        int fy=find(y);
        if(fx!=fy){
            p[fy]=fx;
            root[fx]=merge(root[fx],root[fy],1,n);
        }
    }
    cin>>m;
    while(m--){
        char op;
        int x,y;
        cin>>op>>x>>y;
        if(op=='Q')cout<<id[queryk(root[find(x)],1,n,y)]<<'\n';
        else {
            int fx=find(x);
            int fy=find(y);
            if(fx!=fy){
                p[fy]=fx;
                root[fx]=merge(root[fx],root[fy],1,n);
            }
        }
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

雨天的尾巴

#include
#define update modify
using namespace std;
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],idx,o;
int ls[N*50],rs[N*50],ma[N*50],sum[N*50],n,m,root[N*50];
int sz[N],son[N],top[N],dep[N],fa[N],ans[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dsu(int u,int father=-1){
    sz[u]=1;
    fa[u]=father;
    if(father!=-1)dep[u]=dep[father]+1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==father)continue;
        dsu(j,u);
        sz[u]+=sz[j];
        if(sz[j]>sz[son[u]])son[u]=j;
    }
}
void dfs2(int u,int p){
    top[u]=p;
    if(!son[u])return;
    dfs2(son[u],p);
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa[u]||j==son[u])continue;
        dfs2(j,j);
    }
}
void pushup(int u){
    int l=ls[u];
    int r=rs[u];
    if(ma[l]>ma[r]){
        ma[u]=ma[l];
        sum[u]=sum[l];
    }
    else if(ma[l]<ma[r]){
        ma[u]=ma[r];
        sum[u]=sum[r];
    }
    else{
        ma[u]=ma[l];
        sum[u]=min(sum[l],sum[r]);
    }
}
void modify(int &u,int l,int r,int x,int k){
    if(!u)u=++o;
    if(l==r){
        ma[u]+=k;
        sum[u]=x;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls[u],l,mid,x,k);
    else modify(rs[u],mid+1,r,x,k);
    pushup(u);
}
int merge(int a,int b,int l,int r){
    if(!a||!b)return a|b;
    if(l==r){
        ma[a]+=ma[b];
        return a;
    }
    int mid=l+r>>1;
    ls[a]=merge(ls[a],ls[b],l,mid);
    rs[a]=merge(rs[a],rs[b],mid+1,r);
    pushup(a);
    return a;
}
int lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    return y;
}
void dfs(int u,int faa=-1){
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==faa)continue;
        dfs(j,u);
        root[u]=merge(root[u],root[j],1,1e5);
    }
    // ans[u]=sum[root[u]];
    // return;
    //不能直接写ans[u]=sum[root[u]];
    //因为可能会更新掉一些用不到的节点得到错误答案
    if(ma[root[u]]==0)ans[u]=0;
    else ans[u]=sum[root[u]];
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dsu(1,-1);
    dfs2(1,1);
    while(m--){
        int x,y,z;
        cin>>x>>y>>z;
        int f=lca(x,y);
        update(root[x],1,1e5,z,1);
        update(root[y],1,1e5,z,1);
        update(root[f],1,1e5,z,-1);
        if(fa[f]!=-1)update(root[fa[f]],1,1e5,z,-1);
    }
    dfs(1);
    // for(int i=1;i<=n;i++)cout<
    for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

---

Lomsat gelral

树的节点有颜色，一种颜色占领了一个子树，当且仅当没有其他颜色在这个子树中出现得比它多。求占领每个子树的所有颜色之和 CF600E

#include
using namespace std;
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],idx;
int c[N],o,n,m;
long long ans[N],sum[N*20];
int ma[N*20],ls[N*20],rs[N*20],root[N*20];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void pushup(int u){
    int l=ls[u],r=rs[u];
    if(ma[l]>ma[r]){
        sum[u]=sum[l];
        ma[u]=ma[l];
    }
    else if(ma[l]<ma[r]){
        sum[u]=sum[r];
        ma[u]=ma[r];
    }
    else{
        sum[u]=sum[l]+sum[r];
        ma[u]=ma[l];
    }
}
int merge(int a,int b,int l,int r){
    if(!a)return b;
    if(!b)return a;
    if(l==r){
        ma[a]+=ma[b];
        return a;
    }
    int mid=l+r>>1;
    ls[a]=merge(ls[a],ls[b],l,mid);
    rs[a]=merge(rs[a],rs[b],mid+1,r);
    pushup(a);
    return a;
}
void modify(int &u,int l,int r,int x,int k){
    if(!u)u=++o;
    if(l==r){
        ma[u]+=k;
        sum[u]=x;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls[u],l,mid,x,k);
    else modify(rs[u],mid+1,r,x,k);
    pushup(u);
}
void dfs(int u,int fa){
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        dfs(j,u);
        root[u]=merge(root[u],root[j],1,n);
    }
    modify(root[u],1,n,c[u],1);
    ans[u]=sum[root[u]];
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(1,-1);
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

---

dsu