dsu_on_tree

发表于 更新于 分类于 阅读次数： Changyan：

dsu on tree

DSU on tree ，作为一个比较神奇的算法，常常可以代替树剖/树上莫队来完成一些分别处理以每个根节点为问题核心关于其子树的问题。

本算法的思想就是类似于树剖，每次维护树的重儿子为根的子树，即儿子最多的子树，这样可以保证每个点呗操作一次会使得维护的节点数至少翻倍。因此每个点最多被维护$log{n}$次，总时间复杂度为$O(nlogn)$

模板题：

A - Lomsat gelral

大意是找到以每个点为根节点的子树的主要颜色之和

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
#define int LL
const int N=200010,M=N*2,mod=1e9+7;
int n,m,e[M],ne[M],h[N],sz[N],son[N],color[N],idx;
int sum=0,cnt[N],mx,ans[N];

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs_son(int u,int pre){
    sz[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==pre) continue;
        dfs_son(j ,u);
        if(sz[j]>sz[son[u]]) son[u]=j;
        sz[u]+=sz[j];
    }
}

void modify(int u,int pre,int op,int zson){
    int c=color[u];
    cnt[c] += op;
    if(cnt[c]>mx) mx=cnt[c], sum=c;
    else if(cnt[c]==mx) sum += c;
    
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==pre||j==zson) continue;
        modify(j, u, op, zson);
    }
}

void dfs(int u,int pre,int s){
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==pre||j==son[u]) continue;
        dfs(j, u, 0);
    }
    if(son[u]) dfs(son[u], u, 1);
    modify(u, pre, 1, son[u]);
    ans[u]=sum;
    if(!s) modify(u, pre, -1, 0),sum=0,mx=0;
}

void solve(){
	n=read();
	rep(i,1,n) color[i]=read();
	rep(i,1,n-1){
	    int u=read(),v=read();
	    add(u,v), add(v,u);
	}
	dfs_son(1,-1);
	dfs(1,-1,1);
	for(int i=1;i<=n;++i) printf("%lld ",ans[i]);
}

算是dsu on tree的模板了，先一遍DFS与处理出所有节点的重儿子，然后第二遍dfs的时候先dfs所有的非重儿子,再dfs所有的重儿子来处理答案。有一个优化小技巧，预处理的时候顺便与处理出dfs序，这样就不需要递归修改，改为直接循环修改，这样可以减小代码常熟。

dsu on tree 算是一个越来越板的套路，基本上只要改一改板子，转化一下问题就可以了。

B - Tree Requests

求每一个点特定数量的字符是否可以构成回文串。也是非常的板的一道题目，能不能构成回文串取决于奇数个字符的数量是否不超过2.因此直接再dsu on tree的时候维护一下每个点特定深度下的26个字母的个数即可。

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
#define N 500010
int n,m;
vector<int> edge[N];
int sz[N],dep[N],son[N];
vector<pii> qry[N];
int ans[N];
int cnt[N][27];
int l[N],id[N],r[N],idx=0;
char ch[N];
 
inline void dfs(int u,int pre){
    sz[u]=1,dep[u]=dep[pre]+1;l[u]=++idx,id[idx]=u;
    for(auto v:edge[u]){
        if(v==pre) continue;
        dfs(v, u);
        sz[u] += sz[v];
        if(sz[son[u]]<sz[v]) son[u]=v;
    }
    r[u]=idx;
}
 
inline void add(int u,int d){
    cnt[dep[u]][ch[u]-'a']+=d;
}
 
void dfs(int u,int pre,int top){
    for(auto v:edge[u]){
        if(v==pre||v==son[u]) continue;
        dfs(v, u, 0);
    }
    if(son[u]) dfs(son[u], u, 1);
 
    for(auto v:edge[u]){
        if(v==pre||v==son[u]) continue;
        for(int i=l[v];i<=r[v];++i)
            add(id[i], 1);
    }
    add(u, 1);
        
    for(auto q:qry[u]){
        int tmp=0;
        for(int i=0;i<26;++i){
            if(cnt[q.x][i]&1) tmp++;
        }
        ans[q.y]=(tmp<2);
    }
 
    if(!top) {
        for(int i=l[u];i<=r[u];++i){
            add(id[i], -1);
        }
    }
}
 
void solve(){
	n=read(),m=read();
    rep(i,2,n) {
        int x=read();
        edge[x].push_back(i);
        edge[i].push_back(x);
    }
    scanf("%s",ch+1);
    rep(i,1,m){
        int x=read(),h=read();
        qry[x].push_back({h,i});
    }
    dfs(1,0);
    dfs(1,0,1);
    rep(i,1,m) puts(ans[i]?"Yes":"No");
}

C - Blood Cousins Return

求对于每个点相对深度下不同名字的孙子的数量。将相对深度转化为绝对深度，借助set<string>来维护对应深度的名字数量

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
#define N 500010
int n,m,x,dep[N],sz[N],son[N],l[N],r[N],id[N],idx,ans[N];
string name[N];
set<string> ds[N];
vector<int> edge[N];
vector<pii> qry[N];

void dfs_init(int u,int d){
    l[u]=++idx,id[idx]=u,sz[u]=1,dep[u]=d;
    son[u]=-1;
    for(auto v:edge[u]){
        dfs_init(v, d+1);
        sz[u] += sz[v];
        if(son[u]==-1||sz[v] > sz[son[u]]) son[u]=v;
    }
    r[u]=idx;
}

void dfs(int u,int top){
    for(auto v:edge[u]){
        if(v==son[u]) continue;
        dfs(v, 0);
    }
    if(son[u]!=-1) dfs(son[u], 1);
    for(auto v:edge[u]){
        if(v==son[u]) continue;
        for(int i=l[v];i<=r[v];++i){
            ds[dep[id[i]]].insert(name[id[i]]);
        }
    }
    ds[dep[u]].insert(name[u]);
    for(auto q:qry[u]){
        int k=q.x,id=q.y;
        ans[id]=ds[k].size();
    }
    if(!top){
        for(int i=l[u];i<=r[u];++i)
            ds[dep[id[i]]].erase(name[id[i]]);
    }
}

void solve(){
    cin >> n;
    rep(i,1,n){
        cin >> name[i] >> x;
        edge[x].push_back(i);        
    }
    dfs_init(0,0);  
    cin >> m;
    rep(i,1,m){
        int v,k;
        cin >> v >> k;
        qry[v].push_back({k+dep[v],i});
    }
    dfs(0,1);
    for(int i=1;i<=m;++i) print(ans[i]);
}

D - Blood Cousins

计算给定点v的k级表兄的数量，我们可以转化为v的k级祖先的相对深度为k的子孙的数量，答案直接是-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
60
61
62
63
64
65
66
67
68
69
70
71
72
#define N 200010
vector<int> edge[N];
int n,m,sz[N],dep[N],son[N];
int f[20][N],ans[N];
vector<pii> qry[N];
int l[N],r[N],id[N],idx=0;
int cnt[N];

void dfs_init(int u,int fa,int d){
    sz[u]=1,dep[u]=d,son[u]=-1;
    l[u]=++idx,id[idx]=u;
    for(auto v:edge[u]){
        f[0][v]=u;
        dfs_init(v, u, d+1);
        sz[u] += sz[v];
        if(son[u]==-1||sz[son[u]] < sz[v]) 
            son[u]=v;
    }
    r[u]=idx;
}

void dfs(int u,int top){
    for(auto v:edge[u]){
        if(v==son[u]) 
            continue;
        dfs(v, 0);
    }
    if(son[u]!=-1) dfs(son[u], 1);
    for(auto v:edge[u]){
        if(v==son[u]) continue;
        for(int i=l[v];i<=r[v];++i)
            cnt[dep[id[i]]] ++;
    }
    cnt[dep[u]] ++;
    for(auto v:qry[u]){
        int dp=v.x,id=v.y;
        ans[id]=cnt[dp]-1;
    }
    if(!top){
        for(int i=l[u];i<=r[u];++i)
            cnt[dep[id[i]]] --;
    }
}

int get(int u,int k){
    for(int i=19;i>=0;--i)
        if(k>>i&1) 
            u=f[i][u];
    return u;
}

void solve(){
	n=read();
    rep(i,1,n){
        int x=read();
        edge[x].push_back(i);
    }
    dfs_init(0,0,0);
    for(int i=1;i<=19;++i)
        for(int j=0;j<=n;++j){
            f[i][j]=f[i-1][f[i-1][j]];
        }
    m=read();
    rep(i,1,m){
        int v=read(),p=read();
        int t=get(v,p);
        if(t) qry[t].push_back({dep[t]+p,i});
    }
    dfs(0,1);
    for(int i=1;i<=m;++i) printf("%d ",ans[i]);
}

G - Tree and Queries

这道题要求给定节点的子树中数量不少于给定数的颜色的个数。首先可以对每个点作为根节点来处理子树中的问题，可以用DSU on Tree来解决，其次由于我们不方便直接求得每个颜色对应的个数，因此我们还需要用树状数组来维护每一个个数的颜色数量。

总的时间复杂度为$O(nlog^2n)$

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
// #define int LL
const int N=200010,M=N*2,mod=1e9+7;
int n,m,col[N],sz[N],dep[N],son[N],id[N],l[N],r[N],idx,ans[N];
vector<int> edge[N];
vector<pii> qry[N];
int cnt[N];
struct BIT{
	#define lowbit(x) ((x)&(-x))
	int tr[100005],n;
	void resize(int _n=100000){n=_n;}
	void add(int x,int d){
		for(;x<=n;x+=lowbit(x)) tr[x]+=d;
	}
	int ask(int x){
		int ans=0;
		for(;x;x-=lowbit(x)) ans += tr[x];
		return ans;
	}
}T;

void dfs_init(int u,int pre){
	l[u]=++idx,id[idx]=u;
	dep[u]=dep[pre]+1,sz[u]=1;
	for(auto v:edge[u]){
		if(v==pre) continue;
		dfs_init(v, u);
		sz[u] += sz[v];
		if(sz[son[u]] < sz[v]) son[u]=v;
	}
	r[u]=idx;
}

void dfs(int u,int pre,int up){
	for(auto v:edge[u]){
		if(v!=pre&&v!=son[u])
			dfs(v, u, 0);
	}
	if(son[u]) dfs(son[u], u, 1);
	
	for(auto v:edge[u]){
		if(v==pre||v==son[u]) 
			continue;
		for(int i=l[v];i<=r[v];++i){
			if(cnt[col[id[i]]]) 
				T.add(cnt[col[id[i]]], -1);
			cnt[col[id[i]]] ++;
			T.add(cnt[col[id[i]]], 1);
		}
	}
	if(cnt[col[u]])
		T.add(cnt[col[u]], -1);
	cnt[col[u]] ++;
	T.add(cnt[col[u]], 1);
	
	for(auto tmp:qry[u]){
		int x=tmp.x,id=tmp.y;
		ans[id] = T.ask(T.n);
		if(x>1) ans[id] -= T.ask(x-1);
	}

	if(!up){
		for(int i=l[u];i<=r[u];++i){
			T.add(cnt[col[id[i]]], -1);
			cnt[col[id[i]]] --;
			if(cnt[col[id[i]]])
				T.add(cnt[col[id[i]]], 1);
		}
	}
}

void solve(){
	n=read(),m=read();
	rep(i,1,n)
		col[i]=read();
	rep(i,1,n-1){
		int u=read(),v=read();
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs_init(1,0);
	rep(i,1,m){
		int x=read(),t=read();
		qry[x].push_back({t,i});
	}
	dfs(1,0,1);
	for(int i=1;i<=m;++i)
		print(ans[i]);
}