树链剖分

字数统计: 4k字   |   阅读时长: 24min

P3384 【模板】树链剖分

这道是最基础的树链剖分题目。可以当做复习食用。。

其中维护字数操作：因为它是按照DSF序进行编号的，所以维护序列x到x+siz[x]-1便是维护以x为根的子树。

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
#include<bits/stdc++.h>
using namespace std;

template<typename T>
inline void read(T &a)
{
	T f=1;a=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s<='9'&&s>='0'){a=a*10+s-'0';s=getchar();}
	a*=f;
}

struct node
{
	int ne,to;
}edge[200100];

int cnt,head[100100];

inline void add(int u,int v)
{
	edge[++cnt].ne=head[u];
	edge[cnt].to=v;
	head[u]=cnt;
}

int fa[100100],deep[100100],size[100100],son[100100],w[100100];
int id[100100],top[100100],ww[100100],idx;

void dfs1(int x)
{
	size[x]=1;
	int maxx=0;
	for(register int i=head[x];i;i=edge[i].ne)
	{
		int v=edge[i].to;
		if(v==fa[x]) continue;
		deep[v]=deep[x]+1;
		fa[v]=x;
		dfs1(v);
		size[x]+=size[v];
		if(maxx<size[x]) maxx=size[x],son[x]=v;
	}
}

void dfs2(int x,int topf)
{
	id[x]=++idx;
	top[x]=topf;
	ww[id[x]]=w[x];
	if(!son[x]) return;
	dfs2(son[x],topf);
	for(register int i=head[x];i;i=edge[i].ne)
	{
		int v=edge[i].to;
		if(v==fa[x]||v==son[x]) continue;
		dfs2(v,v);
	}
}

struct tree
{
	int l,r,ls,rs;
	int sum,tag;
}tr[200100];

int tcnt=1;
int n,m,r,p;

inline void update(int x){tr[x].sum=tr[tr[x].ls].sum+tr[tr[x].rs].sum;}

inline void pushdown(int x)
{
	int ls=tr[x].ls,rs=tr[x].rs;
	if(tr[x].tag)
	{
		tr[ls].tag+=tr[x].tag;
		tr[ls].tag%=p;
		tr[ls].sum+=tr[x].tag*(tr[ls].r-tr[ls].l+1)%p;
		tr[ls].sum%=p;
		
		tr[rs].tag+=tr[x].tag;
		tr[rs].tag%=p;
		tr[rs].sum+=tr[x].tag*(tr[rs].r-tr[rs].l+1)%p;
		tr[rs].sum%=p;
		
		tr[x].tag=0;
	}
}

void build(int x,int l,int r)
{
	tr[x].l=l,tr[x].r=r;
	if(l==r)
	{
		tr[x].sum=ww[l];
		return;
	}
	int mid=(l+r)>>1;
	tr[x].ls=++tcnt;build(tr[x].ls,l,mid);
	tr[x].rs=++tcnt;build(tr[x].rs,mid+1,r);
	update(x);
} 

void change(int x,int l,int r,int v)
{
	if(l<=tr[x].l&&tr[x].r<=r)
	{
		tr[x].sum+=v*(tr[x].r-tr[x].l+1)%p;
		tr[x].sum%=p;
		tr[x].tag+=v;
		tr[x].tag%=p;
		return;
	}
	pushdown(x);
	int mid=(tr[x].l+tr[x].r)>>1;
	if(l<=mid) change(tr[x].ls,l,r,v);
	if(r>mid) change(tr[x].rs,l,r,v);
	update(x);
}

int query(int x,int l,int r)
{
	int rt=0;
	if(l<=tr[x].l&&tr[x].r<=r) return tr[x].sum;
	pushdown(x);
	int mid=(tr[x].l+tr[x].r)>>1;
	if(l<=mid) rt+=query(tr[x].ls,l,r),rt%=p;
	if(r>mid) rt+=query(tr[x].rs,l,r),rt%=p;
	return rt;
}

inline void query_add(int x,int y,int v)
{
	v%=p;
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]]) swap(x,y);
		change(1,id[top[x]],id[x],v);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	change(1,id[x],id[y],v);
}

inline int query_sum(int x,int y)
{
	int rt=0;
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]]) swap(x,y);
		rt+=query(1,id[top[x]],id[x]);
		rt%=p;
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	rt+=query(1,id[x],id[y]);
	rt%=p;
	return rt;
}

inline void qson_add(int x,int v)
{
	change(1,id[x],id[x]+size[x]-1,v%p);
}

inline int qson_sum(int x)
{
	return query(1,id[x],id[x]+size[x]-1);
}

int opt,x,y,z;

int main()
{
	read(n),read(m),read(r),read(p);
	for(register int i=1;i<=n;i++) read(w[i]);
	int u,v;
	for(register int i=1;i<n;i++)
	{
		read(u),read(v);
		add(u,v);add(v,u);
	}
	dfs1(r);
	
	dfs2(r,r);
	build(1,1,n);
	for(register int i=1;i<=m;i++)
	{
		read(opt);read(x);
		if(opt!=4) read(y);
		if(opt==1)
		{
			read(z);
			query_add(x,y,z);
		}	
		else if(opt==2)
		{
			printf("%d\n",query_sum(x,y));
		}
		else if(opt==3)
		{
			qson_add(x,y);
		}
		else printf("%d\n",qson_sum(x));
	}
	return 0;
}

P2590 [ZJOI2008]树的统计

一道简单的模板题

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include<bits/stdc++.h>
using namespace std;

template<typename T>
inline void read(T &a)
{
	T f=1;a=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s<='9'&&s>='0'){a=a*10+s-'0';s=getchar();}
	a*=f;
}

struct node
{
	int ne,to;
}edge[60100];

int head[30100],cnt,w[30100];

inline void add(int u,int v)
{
	edge[++cnt].ne=head[u];
	edge[cnt].to=v;
	head[u]=cnt;
}

int fa[30100],siz[30100],son[30100],dep[30100];

void dfs1(int x)
{
	siz[x]=1;
	int maxx=-1;
	for(register int i=head[x];i;i=edge[i].ne)
	{
		int v=edge[i].to;
		if(v==fa[x]) continue;
		fa[v]=x;
		dep[v]=dep[x]+1;
		dfs1(v);
		siz[x]+=siz[v];
		if(maxx<siz[v]) maxx=siz[v],son[x]=v;
	}
}

int top[30100],wt[30100],id[30100],idx;

void dfs2(int x,int topf)
{
	id[x]=++idx;
	wt[idx]=w[x];
	top[x]=topf;
	if(!son[x]) return;
	dfs2(son[x],topf);
	for(register int i=head[x];i;i=edge[i].ne)
	{
		int v=edge[i].to;
		if(v==fa[x]||v==son[x]) continue;
		dfs2(v,v);
	}
}

struct tree
{
	int ls,rs,l,r;
	int sum,mx;
}tr[60100];

int tcnt=1;

inline void update(int x)
{
	tr[x].sum=tr[tr[x].ls].sum+tr[tr[x].rs].sum;
	tr[x].mx=max(tr[tr[x].ls].mx,tr[tr[x].rs].mx);
}

void build(int x,int l,int r)
{
	tr[x].l=l;tr[x].r=r;
	if(l==r)
	{
		tr[x].sum=tr[x].mx=wt[l];
		return;
	}
	int mid=(l+r)>>1;
	tr[x].ls=++tcnt;build(tr[x].ls,l,mid);
	tr[x].rs=++tcnt;build(tr[x].rs,mid+1,r);
	update(x);
}

int query_sum(int x,int l,int r)
{
	int rt=0;
	if(l<=tr[x].l&&tr[x].r<=r) return tr[x].sum;
	int mid=(tr[x].l+tr[x].r)>>1;
	if(l<=mid) rt+=query_sum(tr[x].ls,l,r);
	if(r>mid) rt+=query_sum(tr[x].rs,l,r);
	return rt;
}

int query_max(int x,int l,int r)
{
	int rt=INT_MIN;
	if(l<=tr[x].l&&tr[x].r<=r) return tr[x].mx;
	int mid=(tr[x].l+tr[x].r)>>1;
	if(l<=mid) rt=max(query_max(tr[x].ls,l,r),rt);
	if(r>mid) rt=max(query_max(tr[x].rs,l,r),rt);
	return rt;
}

void change(int x,int l,int v)
{
	if(tr[x].l==tr[x].r) 
	{
		tr[x].sum=tr[x].mx=v;
		return;
	}
	int mid=(tr[x].l+tr[x].r)>>1;
	if(l<=mid) change(tr[x].ls,l,v);
	else change(tr[x].rs,l,v);
	update(x);
}

inline int query1(int x,int y)
{
	int rt=INT_MIN;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		rt=max(rt,query_max(1,id[top[x]],id[x]));
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	rt=max(rt,query_max(1,id[x],id[y]));
	return rt;
}

inline int query2(int x,int y)
{
	int rt=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		rt+=query_sum(1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	rt+=query_sum(1,id[x],id[y]);
	return rt;
}

int n,q,x,y;
char opt[10];

int main()
{
	read(n);
	int u,v;
	for(register int i=1;i<n;i++) 
	{
		read(u),read(v);
		add(u,v),add(v,u);
	}
	for(register int i=1;i<=n;i++) read(w[i]);
	dfs1(1);
	dfs2(1,1);
	build(1,1,n);
	read(q);
	for(register int i=1;i<=q;i++)
	{
		scanf("%s",opt);
		read(x),read(y);
		if(opt[0]=='C')
		{
			change(1,id[x],y);
		}
		else if(opt[1]=='M')
		{
			printf("%d\n",query1(x,y));
		}
		else printf("%d\n",query2(x,y));
	}
	return 0;
}

P2486 [SDOI2011]染色

这道题比较有意思，该题的关键是每一次求区间的和时，都要判断拼接的两段区间的端点颜色是否相同。

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include<bits/stdc++.h>
using namespace std;

template<typename T>
inline void read(T &a)
{
    T f=1;a=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s<='9'&&s>='0'){a=a*10+s-'0';s=getchar();}
    a*=f;
}

struct node
{
    int ne,to;
}edge[201000];

int head[101000],cnt;

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].ne=head[u];
    head[u]=cnt;
}

int son[100100],siz[101000],dep[101000],fa[100100];

void dfs1(int x)
{
    siz[x]=1;
    int mx=-1;
    for(register int i=head[x];i;i=edge[i].ne)
    {
        int v=edge[i].to;
        if(v==fa[x]) continue;
        dep[v]=dep[x]+1;
        fa[v]=x;
        dfs1(v);
        siz[x]+=siz[v];
        if(siz[v]>mx) mx=siz[v],son[x]=v; 
    }
}

int top[101000],idx,wt[101000],id[101000],w[101000];

void dfs2(int x,int topf)
{
    id[x]=++idx;
    wt[idx]=w[x];
    top[x]=topf;
    if(!son[x]) return;
    dfs2(son[x],topf);
    for(register int i=head[x];i;i=edge[i].ne)
    {
        int v=edge[i].to;
        if(v==fa[x]||v==son[x]) continue;
        dfs2(v,v);
    }
}

struct tree
{
    int l,r,ls,rs;
    int tag,sum,lx,rx;
}tr[201000];

inline void update(int x)
{
    tr[x].sum=tr[tr[x].ls].sum+tr[tr[x].rs].sum;
    tr[x].lx=tr[tr[x].ls].lx;
    tr[x].rx=tr[tr[x].rs].rx;
    if(tr[tr[x].ls].rx==tr[tr[x].rs].lx) tr[x].sum--;
}

inline void pushdown(int x)
{
    int ls=tr[x].ls,rs=tr[x].rs;
    if(tr[x].tag)
    {
        tr[ls].tag=tr[x].tag;
        tr[rs].tag=tr[x].tag;
        tr[ls].lx=tr[ls].rx=tr[x].tag;
        tr[rs].lx=tr[rs].rx=tr[x].tag;
        tr[rs].sum=tr[ls].sum=1;
        tr[x].tag=0;
    }
}

int tcnt=1,ql,qr;

void build(int x,int l,int r)
{
    tr[x].l=l,tr[x].r=r;
    if(l==r)
    {
        tr[x].lx=tr[x].rx=wt[l];
        tr[x].sum=1;
        return;
    }
    int mid=(l+r)>>1;
    tr[x].ls=++tcnt;build(tr[x].ls,l,mid);
    tr[x].rs=++tcnt;build(tr[x].rs,mid+1,r);
    update(x);
}

void change(int x,int l,int r,int v)
{
    if(l<=tr[x].l&&tr[x].r<=r)
    {
        tr[x].tag=v;
        tr[x].lx=tr[x].rx=v;
        tr[x].sum=1;
        return;
    }
    pushdown(x);
    int mid=(tr[x].l+tr[x].r)>>1;
    if(l<=mid) change(tr[x].ls,l,r,v);
    if(r>mid) change(tr[x].rs,l,r,v);
    update(x);
}

int query(int x,int l,int r)
{
    int rt=0,lx=0,rx=0;
    if(l<=tr[x].l&&tr[x].r<=r) 
    {
        if(l==tr[x].l) ql=tr[x].lx;
        if(r==tr[x].r) qr=tr[x].rx;
        return tr[x].sum;
    }
    pushdown(x);
    int mid=(tr[x].l+tr[x].r)>>1;
    if(l<=mid) rt+=query(tr[x].ls,l,r),rx=tr[tr[x].ls].rx;
    if(r>mid) rt+=query(tr[x].rs,l,r),lx=tr[tr[x].rs].lx;
    if(rx&&lx&&lx==rx) rt--;
    return rt;
}

inline void C(int x,int y,int v)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        change(1,id[top[x]],id[x],v);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    change(1,id[x],id[y],v);
}

inline int Q(int x,int y)
{
    int rt=0,tmpx=-1,tmpy=-1;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y),swap(tmpx,tmpy);
        rt+=query(1,id[top[x]],id[x]);
        if(tmpx&&tmpx==qr) rt--; 
        tmpx=ql;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y),swap(tmpx,tmpy);
    rt+=query(1,id[x],id[y]);
    if(tmpx&&tmpx==ql) rt--; //(tmpx==qr)是错的，因为这个我调了一晚上的bug。。。
    if(tmpy&&tmpy==qr) rt--;
    qr=ql=0;//全局变量需清零 
    return rt;
}

int n,m,opt[5];

int main()
{
    read(n),read(m);
    for(register int i=1;i<=n;i++) read(w[i]);
    int u,v,z;
    for(register int i=1;i<n;i++)
    {
        read(u),read(v);
        add(u,v),add(v,u);
    }
    dfs1(1);
    dfs2(1,1);
    build(1,1,n);
    for(register int i=1;i<=m;i++)
    {
        scanf("%s",opt);
        read(u),read(v);
        if(opt[0]=='C')
        {
            read(z);
            C(u,v,z);
        }
        if(opt[0]=='Q')
        {
            printf("%d\n",Q(u,v));
        }
    }
    return 0;
}

P4315 月下“毛景树”

一道恶心的码农题。。。该题需要注意的是tag下传的优先级。（遇到将区间修改为某值的题时，可以用两个变量，tag和v分别记录是否被修改以及修改为多少）

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
#include<bits/stdc++.h>
using namespace std;

template<typename T>
inline void read(T &a)
{
	T f=1;a=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){a=a*10+s-'0';s=getchar();}
	a*=f;
}

struct node
{
	int ne,to,w;
}edge[201000];

int head[100100],cnt;

inline void add(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].ne=head[u];
	edge[cnt].w=w;
	head[u]=cnt;
}

int n,w[100100];

int fa[100100],siz[100100],son[100100],dep[100100];

int num[100100],wt[100100];//num[x]第x条边的边权所在点的新编号。 

void dfs1(int x)
{
	siz[x]=1;
	int mx=-1;
	for(register int i=head[x];i;i=edge[i].ne)
	{
		int v=edge[i].to;
		if(v==fa[x]) continue;
		dep[v]=dep[x]+1;
		w[v]=edge[i].w;
		fa[v]=x;
		dfs1(v);
		siz[x]+=siz[v];
		if(siz[v]>mx) mx=siz[v],son[x]=v;
	}
}

int idx,id[100100],top[100100];

void dfs2(int x,int topf)
{
	id[x]=++idx;
	wt[idx]=w[x];
	top[x]=topf;
	if(!son[x]) return;
	dfs2(son[x],topf);
	for(register int i=head[x];i;i=edge[i].ne)
	{
		int v=edge[i].to;
		if(v==fa[x]||v==son[x]) continue;
		dfs2(v,v);
	}
}

int tcnt=1;

struct tree
{
	int l,r,rs,ls;
	int mx,add,tag,v;//tag记录该区间是否被修改为同一个值，v为该值。 
}tr[200100];

inline void update(int x){tr[x].mx=max(tr[tr[x].ls].mx,tr[tr[x].rs].mx);}

inline void pushdown(int x)
{
	int ls=tr[x].ls,rs=tr[x].rs;
	if(tr[x].tag)
	{
		tr[ls].tag=tr[rs].tag=1;
		tr[ls].add=tr[rs].add=0;
		tr[ls].mx=tr[rs].mx=tr[x].v;
		tr[ls].v=tr[rs].v=tr[x].v;
		tr[x].tag=0; 
	}
	if(tr[x].add)
	{
		tr[ls].add+=tr[x].add;
		tr[rs].add+=tr[x].add;
		tr[ls].mx+=tr[x].add;
		tr[rs].mx+=tr[x].add;
		tr[x].add=0;
	}
}

void build(int x,int l,int r)
{
	tr[x].l=l;tr[x].r=r;
	if(l==r)
	{
		tr[x].mx=wt[l];
		return;
	}
	int mid=(l+r)>>1;
	tr[x].ls=++tcnt;build(tr[x].ls,l,mid);
	tr[x].rs=++tcnt;build(tr[x].rs,mid+1,r);
	update(x);
}

void point_modify(int x,int l,int v)
{
	if(tr[x].l==tr[x].r)
	{
		tr[x].tag=tr[x].v=tr[x].add=0;
		tr[x].mx=v;
		return;
	}
	pushdown(x);
	int mid=(tr[x].l+tr[x].r)>>1;
	if(l<=mid) point_modify(tr[x].ls,l,v);
	else point_modify(tr[x].rs,l,v);
	update(x);
}

void query_modify1(int x,int l,int r,int v)
{
	if(l<=tr[x].l&&tr[x].r<=r)
	{
		tr[x].tag=1;
		tr[x].add=0;
		tr[x].v=v;
		tr[x].mx=v;
		return;
	}
	pushdown(x);
	int mid=(tr[x].l+tr[x].r)>>1;
	if(l<=mid) query_modify1(tr[x].ls,l,r,v);
	if(r>mid) query_modify1(tr[x].rs,l,r,v);
	update(x);
}

void query_modify2(int x,int l,int r,int v)
{
	if(l<=tr[x].l&&tr[x].r<=r)
	{
		tr[x].add+=v;
		tr[x].mx+=v;
		return;
	}
	pushdown(x);
	int mid=(tr[x].l+tr[x].r)>>1;
	if(l<=mid) query_modify2(tr[x].ls,l,r,v);
	if(r>mid) query_modify2(tr[x].rs,l,r,v);
	update(x);
}

int query_max(int x,int l,int r)
{
	int mx=-2e9;
	if(l<=tr[x].l&&tr[x].r<=r) return tr[x].mx;
	pushdown(x);
	int mid=(tr[x].l+tr[x].r)>>1;
	if(l<=mid) mx=max(query_max(tr[x].ls,l,r),mx);
	if(r>mid) mx=max(query_max(tr[x].rs,l,r),mx);
	return mx;
}

inline void cover(int x,int y,int z)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		query_modify1(1,id[top[x]],id[x],z);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	if(x!=y) query_modify1(1,id[x]+1,id[y],z);
}

inline void Add(int x,int y,int z)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		query_modify2(1,id[top[x]],id[x],z);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	if(x!=y) query_modify2(1,id[x]+1,id[y],z);
}

inline int Max(int x,int y)
{
	int mx=-2e9;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		mx=max(mx,query_max(1,id[top[x]],id[x]));
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	if(x!=y) mx=max(mx,query_max(1,id[x]+1,id[y]));
	return mx;
}

int u[100100],v[100100];
char opt[10];

int main()
{
	freopen("1.in","r",stdin);
	freopen("111.out","w",stdout);
	read(n);
	for(register int i=1;i<n;i++) 
	{
		read(u[i]),read(v[i]),read(w[i]);
		add(u[i],v[i],w[i]);add(v[i],u[i],w[i]);
	}
	dfs1(1);
	dfs2(1,1);
	for(register int i=1;i<=n;i++)
	{
		if(u[i]!=fa[v[i]]) swap(u[i],v[i]);
		num[i]=id[v[i]];
	}
	build(1,1,n);
	int x,y,z;
	while(~scanf("%s",opt)&&opt[0]!='S')
	{
		read(x),read(y);
		if(opt[0]=='C')
		{
			if(opt[1]=='h') point_modify(1,num[x],y);
			else
			{
				read(z);
				cover(x,y,z);
			}
		}
		if(opt[0]=='A')
		{
			read(z);
			Add(x,y,z);
		}
		if(opt[0]=='M')
		{
			printf("%d\n",Max(x,y));
		}
	}
	return 0;
}
本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/7e454910.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

    			  jsonContent:
				meta: false
				pages: false
				posts:
				  title: true
				  date: true
				  path: true
				  text: false
				  raw: false
				  content: false
				  slug: false
				  updated: false
				  comments: false
				  link: false
				  permalink: false
				  excerpt: false
				  categories: false
				  tags: true


There's nothing