题解 P1505 【[国家集训队]旅游】
题解：
巨细节的一道题。
关于之前的题解（截止至2020.10.21之前）为什么错了，请见这个讨论：
关于题解错误的一些看法
感谢管理员的关注和处理。
很明显的树剖题。
树剖不会的走这边：
浅谈树链剖分
首先要边转点，边转点的规则是把边权转到儿子节点上。这样在链修改的时候，要刨除LCA的点权。很好理解。
然后是取相反数的操作。维护一个lazy标记，在打标记的时候容易发现的性质是：对于线段树上的当前节点，新和就是和取反，新最大值是原最小值取反，新最小值是原最大值取反。
那么这道题的思维部分就完事了，无脑开码即可。
注意几个蒟蒻曾经错过的细节：
首先，刨除LCA点权时，要判断x,y是否在一个点上，这时不需要刨，直接返回就行。
之后，lazy标记有没有重复标记。这是指，对于一个点，打两次lazy标记等于没打标记。这个可以通过异或运算来维护。
可以选择使用结构体存线段树，码量会少很多。当然也可以像蒟蒻，写很多函数来维护三个不同值，效果是一样的。
附上5K代码：
#include<cstdio>
#include<algorithm>
#define lson pos<<1
#define rson pos<<1|1
using namespace std;
const int maxn=2*1e5+10;
const int INF=1e9;
int n,m;
int tot,head[maxn],to[maxn<<1],nxt[maxn<<1],val[maxn<<1];
int cnt,son[maxn],top[maxn],id[maxn],deep[maxn],fa[maxn],size[maxn],a[maxn],w[maxn];
char opt[10];
int sum[maxn<<2],mx[maxn<<2],mn[maxn<<2];
int lazy[maxn<<2];
struct edge
{
int x,y;
}idx[maxn];
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<48||ch>57)
if(ch=='-')
f=-1,ch=getchar();
while(ch>=48&&ch<=57)
x=x*10+ch-48,ch=getchar();
return x*f;
}
void add(int x,int y,int z)
{
to[++tot]=y;
nxt[tot]=head[x];
val[tot]=z;
head[x]=tot;
}
void dfs1(int x,int f)
{
deep[x]=deep[f]+1;
fa[x]=f;
size[x]=1;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==f)
continue;
dfs1(y,x);
a[y]=val[i];
size[x]+=size[y];
if(!son[x]||size[y]>size[son[x]])
son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
id[x]=++cnt;
w[cnt]=a[x];
if(!son[x])
return;
dfs2(son[x],t);
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==fa[x]||y==son[x])
continue;
dfs2(y,y);
}
}
void pushup(int pos)
{
sum[pos]=sum[lson]+sum[rson];
mx[pos]=max(mx[lson],mx[rson]);
mn[pos]=min(mn[lson],mn[rson]);
}
void build(int pos,int l,int r)
{
int mid=(l+r)>>1;
if(l==r)
{
sum[pos]=mx[pos]=mn[pos]=w[l];
return;
}
build(lson,l,mid);
build(rson,mid+1,r);
pushup(pos);
}
void mark(int pos,int l,int r)
{
lazy[pos]^=1;
int tmp1=-sum[pos],tmp2=-mn[pos],tmp3=-mx[pos];
sum[pos]=tmp1;
mx[pos]=tmp2;
mn[pos]=tmp3;
}
void pushdown(int pos,int l,int r)
{
int mid=(l+r)>>1;
if(lazy[pos])
{
mark(lson,l,mid);
mark(rson,mid+1,r);
lazy[pos]=0;
}
}
void update(int pos,int l,int r,int x,int k)
{
int mid=(l+r)>>1;
if(l==r)
{
sum[pos]=mx[pos]=mn[pos]=k;
return;
}
pushdown(pos,l,r);
if(x<=mid)
update(lson,l,mid,x,k);
else
update(rson,mid+1,r,x,k);
pushup(pos);
}
void change(int pos,int l,int r,int x,int y)
{
int mid=(l+r)>>1;
if(x<=l && r<=y)
{
mark(pos,l,r);
return;
}
pushdown(pos,l,r);
if(x<=mid)
change(lson,l,mid,x,y);
if(y>mid)
change(rson,mid+1,r,x,y);
pushup(pos);
}
int query_sum(int pos,int l,int r,int x,int y)
{
int ret=0;
int mid=(l+r)>>1;
if(x<=l && r<=y)
return sum[pos];
pushdown(pos,l,r);
if(x<=mid)
ret+=query_sum(lson,l,mid,x,y);
if(y>mid)
ret+=query_sum(rson,mid+1,r,x,y);
return ret;
}
int query_max(int pos,int l,int r,int x,int y)
{
int ret=-INF;
int mid=(l+r)>>1;
if(x<=l && r<=y)
return mx[pos];
pushdown(pos,l,r);
if(x<=mid)
ret=max(ret,query_max(lson,l,mid,x,y));
if(y>mid)
ret=max(ret,query_max(rson,mid+1,r,x,y));
return ret;
}
int query_min(int pos,int l,int r,int x,int y)
{
int ret=INF;
int mid=(l+r)>>1;
if(x<=l && r<=y)
return mn[pos];
pushdown(pos,l,r);
if(x<=mid)
ret=min(ret,query_min(lson,l,mid,x,y));
if(y>mid)
ret=min(ret,query_min(rson,mid+1,r,x,y));
return ret;
}
void chain_upd(int x,int y)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])
swap(x,y);
change(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(deep[x]<deep[y])
swap(x,y);
if(x!=y)
change(1,1,n,id[y]+1,id[x]);
}
int q_sum(int x,int y)
{
int ret=0;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])
swap(x,y);
ret+=query_sum(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(deep[x]<deep[y])
swap(x,y);
if(x!=y)
ret+=query_sum(1,1,n,id[y]+1,id[x]);
return ret;
}
int q_max(int x,int y)
{
int ret=-INF;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])
swap(x,y);
ret=max(ret,query_max(1,1,n,id[top[x]],id[x]));
x=fa[top[x]];
}
if(deep[x]<deep[y])
swap(x,y);
if(x!=y)
ret=max(ret,query_max(1,1,n,id[y]+1,id[x]));
return ret;
}
int q_min(int x,int y)
{
int ret=INF;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])
swap(x,y);
ret=min(ret,query_min(1,1,n,id[top[x]],id[x]));
x=fa[top[x]];
}
if(deep[x]<deep[y])
swap(x,y);
if(x!=y)
ret=min(ret,query_min(1,1,n,id[y]+1,id[x]));
return ret;
}
int main()
{
n=read();
for(int i=1;i<n;i++)
{
int x,y,z;
x=read();y=read();z=read();
x++,y++;
idx[i].x=x;
idx[i].y=y;
add(x,y,z);
add(y,x,z);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
m=read();
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%s%d%d",opt+1,&a,&b);
if(opt[1]=='C')
{
int goal=deep[idx[a].x]>deep[idx[a].y]?idx[a].x:idx[a].y;
update(1,1,n,id[goal],b);
}
else if(opt[1]=='N')
{
a++,b++;
chain_upd(a,b);
}
else if(opt[1]=='S')
{
a++,b++;
printf("%d\n",q_sum(a,b));
}
else if(opt[1]=='M'&&opt[2]=='A')
{
a++,b++;
printf("%d\n",q_max(a,b));
}
else if(opt[1]=='M'&&opt[2]=='I')
{
a++,b++;
printf("%d\n",q_min(a,b));
}
}
return 0;
}