题目
题目描述
输入格式
输出格式
样例
样例输入
1 | 3 |
样例输出
1 | 1 |
题解
SP375的变体，树链剖分好题一个lazy标志传递错误让我调了半天……
先把边权化为点权，建一张新图
对这张新图跑树链剖分，建一棵线段树来维护区间最大和最小值（正常是只需要最大值，但是因为要去相反数，所以需要维护最小值）
对于$3$个操作：
- 修改单边权：直接单点修改就可以了
- 路径取反：划分一下重链，直接区间修改，最大值和最小值取反后交换就好了
- 路径查询：划分重链，直接区间查询最大值
附上代码：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
using namespace std;
struct Segment_Tree
{
int l,r,max,min,add;
}t[400010];
int n,tot,U[100010],V[100010],head[100010],to[200010],ver[200010],nxt[200010],big[100010];
int cnt,top[100010],dep[100010],siz[100010],dfn[100010],fa[100010],wei[100010],sor[100010],p[100010];
char op[10];
void add(int u,int v,int w)
{
nxt[++tot]=head[u],head[u]=tot,to[tot]=v,ver[tot]=w;
}
void dfs1(int u,int Fa)
{
fa[u]=Fa,dep[u]=dep[Fa]+1,siz[u]=1;
for(int i=head[u];i;i=nxt[i]) if(to[i]!=Fa){
wei[to[i]]=ver[i],dfs1(to[i],u),siz[u]+=siz[to[i]],p[(i-1)/2+1]=to[i];
if((!big[u])||siz[to[i]]>siz[big[u]]) big[u]=to[i];
}
}
void dfs2(int u,int Top)
{
dfn[u]=++cnt,sor[cnt]=u,top[u]=Top;
if(!big[u]) return;
dfs2(big[u],Top);
for(int i=head[u];i;i=nxt[i]) if(to[i]!=fa[u]&&to[i]!=big[u]) dfs2(to[i],to[i]);
}
void build(int p,int l,int r)
{
l(p)=l,r(p)=r,d(p)=0x7fffffff,x(p)=-0x7fffffff,a(p)=0;
if(l==r){d(p)=x(p)=wei[sor[l]];return;}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
d(p)=max(d(p*2),d(p*2+1)),x(p)=min(x(p*2),x(p*2+1));
}
void spread(int p)
{
if(a(p)){
int temp,add=a(p);
a(p)=0;
if(!(add&1)) return;
temp=d(p*2),d(p*2)=-x(p*2),x(p*2)=-temp,a(p*2)+=add;
temp=d(p*2+1),d(p*2+1)=-x(p*2+1),x(p*2+1)=-temp,a(p*2+1)+=add;
}
}
void change(int p,int x,int d)
{
if(l(p)==r(p)){d(p)=x(p)=d;return;}
spread(p);
int mid=(l(p)+r(p))/2;
if(x<=mid) change(p*2,x,d);
else change(p*2+1,x,d);
d(p)=max(d(p*2),d(p*2+1)),x(p)=min(x(p*2),x(p*2+1));
}
void Negate(int p,int l,int r)
{
if(l(p)>=l&&r(p)<=r){int temp=d(p);d(p)=-x(p),x(p)=-temp,a(p)++;return;}
spread(p);
int mid=(l(p)+r(p))/2;
if(l<=mid) Negate(p*2,l,r);
if(r>mid) Negate(p*2+1,l,r);
d(p)=max(d(p*2),d(p*2+1)),x(p)=min(x(p*2),x(p*2+1));
}
long long ask(int p,int l,int r)
{
if(l(p)>=l&&r(p)<=r){return d(p);}
spread(p);
int mid=(l(p)+r(p))/2;
long long ans=-0x7fffffff;
if(l<=mid) ans=max(ans,ask(p*2,l,r));
if(r>mid) ans=max(ans,ask(p*2+1,l,r));
return ans;
}
int main()
{
cin>>n;
for(int i=1,u,v,w;i<n;i++) scanf("%d%d%d",&u,&v,&w),U[i]=u,V[i]=v,add(u,v,w),add(v,u,w);
dfs1(1,0),dfs2(1,0);
build(1,1,n);
while(1){
int a,b;
cin>>op;
if(op[0]=='D') break;
scanf("%d%d",&a,&b);
if(op[0]=='C') change(1,dfn[p[a]],b);
if(op[0]=='N'){
for(int ta=top[a],tb=top[b];ta!=tb;)
if(dep[ta]>dep[tb]) Negate(1,dfn[ta],dfn[a]),a=fa[ta],ta=top[a];
else Negate(1,dfn[tb],dfn[b]),b=fa[tb],tb=top[b];
if(a==b) continue;
if(dep[a]<dep[b]) Negate(1,dfn[big[a]],dfn[b]);
else Negate(1,dfn[big[b]],dfn[a]);
}
if(op[0]=='Q'){
long long ans=-0x7fffffff;
for(int ta=top[a],tb=top[b];ta!=tb;)
if(dep[ta]>dep[tb]) ans=max(ans,ask(1,dfn[ta],dfn[a])),a=fa[ta],ta=top[a];
else ans=max(ans,ask(1,dfn[tb],dfn[b])),b=fa[tb],tb=top[b];
if(a==b){printf("%lld\n",ans);continue;}
if(dep[a]<dep[b]) ans=max(ans,ask(1,dfn[big[a]],dfn[b]));
else ans=max(ans,ask(1,dfn[big[b]],dfn[a]));
printf("%lld\n",ans);
}
}
}