【线段树合并】洛谷 P4556 雨天的尾巴【模板】线段树合并
2021-08-09 17:41:00 # ACM

线段树合并；

对于每一个点开一颗权值线段树，采用树上差分的形式维护；

例如在$x,y$之间的路径加上一个$z$的救济粮，那么就在$x$的权值线段树$z$的位置$+1$，在$y$的权值线段树$z$的位置$+1$，在$lca(x,y)$的权值线段树$z$的位置$-1$，在$fa[lca(x,y)]$的权值线段树$z$的位置$-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
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define eps 1e-9
	#define mod 1000000007
	#define MAXN 100005
	#define MS 100005

int n,m;
vector<int > vc[MS];
int fa[MS], dep[MS], sz[MS], zson[MS], top[MS];
struct node{
	int l,r;
	int val;
}p[MAXN*70];
int tot, rtpos[MS];
int ac[MS];

void dfs1(int u,int f){
	fa[u] = f;
	dep[u] = dep[f] + 1;
	sz[u] = 1;
	zson[u] = 0;
	int maxnzson = 0;
	for(auto v:vc[u]){
		if(v != f){
			dfs1(v,u);
			sz[u] += sz[v];
			if(sz[v] > maxnzson){
				maxnzson = sz[v];
				zson[u] = v;
			}
		}
	}
}

void dfs2(int u,int tp){
	top[u] = tp;
	if(zson[u]) dfs2(zson[u],tp);
	for(auto v:vc[u]){
		if(v != fa[u] && v != zson[u]){
			dfs2(v,v);
		}
	}
}

int lca(int u,int v){
	while(top[u] != top[v]){
		if(dep[ top[u] ] < dep[ top[v] ]) swap(u,v);
		u = fa[ top[u] ];
	}
	return dep[u]<dep[v]? u:v;
}

void push_up(int rt){
	p[rt].val = max(p[p[rt].l].val,p[p[rt].r].val);
}

void modify(int pos,int l,int r,int &rt,int val){
	if(!rt) rt = ++tot;
	if(l == r){
		p[rt].val += val;
		return;
	}
	int m = l+r>>1;
	if(m >= pos) modify(pos,l,m,p[rt].l,val);
	else modify(pos,m+1,r,p[rt].r,val);
	push_up(rt);
}

void merge(int &x,int y,int l,int r){
	if(!x || !y) x |= y;
	else if(l == r) p[x].val += p[y].val;
	else{
		int m = l+r>>1;
		merge(p[x].l,p[y].l,l,m);
		merge(p[x].r,p[y].r,m+1,r);
		push_up(x);
	}
}

int query(int l,int r,int rt){
	if(l == r) return l;
	int m = l+r>>1;
	if(p[p[rt].l].val >= p[p[rt].r].val) return query(l,m,p[rt].l);
	else return query(m+1,r,p[rt].r);
}

void dfs(int u){
	for(auto v:vc[u]){
		if(v != fa[u]){
			dfs(v);
			merge(rtpos[u],rtpos[v],1,MAXN);
		}
	}
	ac[u] = query(0,MAXN,rtpos[u]);
}

void solve(){
	cin >> n >> m;
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin >> u >> v;
		vc[u].push_back(v);
		vc[v].push_back(u);
	}
	// 树剖求 lca 
	dfs1(1,0);
	dfs2(1,0);
	while(m--){
		int x,y,z;
		cin >> x >> y >> z;
		modify(z,0,MAXN,rtpos[x],1);
		modify(z,0,MAXN,rtpos[y],1);
		modify(z,0,MAXN,rtpos[lca(x,y)],-1);
		modify(z,0,MAXN,rtpos[fa[lca(x,y)]],-1);
//		cout << "lca(x,y): " << lca(x,y) << "\n";
//		cout << "fa[lca(x,y)]: " << fa[lca(x,y)] << "\n";
	}
	dfs(1);
	for(int i=1;i<=n;i++){
		cout << ac[i] << "\n";
	}
} 

int main() {
	ios::sync_with_stdio(false);
	int ce;
	ce = 1;
//	cin >> ce;
//	scanf("%d",&ce);
	while(ce--){
		solve();
	}



	return 0;
}
/*


*/
Prev
2021-08-09 17:41:00 # ACM
Next