[文章目录]
Description
给你一颗n个节点带有边权的树，给出m次操作。1.更改一条边的边权。2.两点之间路径上的边的边权变为相反数。3.查询两点路径上的边中边权最大，最小值。4.查询两点路径上边权和。
n<=20000,m<=20000
树链剖分。取相反数相当于直接将维护的mx[],mi[],取相反数再swap，sum直接变成相反数。
和毛景树一样，边权转化到点上，lca不查。
压了一下行，哈哈哈
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 201000
using namespace std;
int n,m; char st[30];
int head[N],to[N<<1],nxt[N<<1],data[N<<1],id[N<<1],cnt;
void add(int x,int y,int z,int zz){to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; data[cnt]=z; id[cnt]=zz;}
int fa[N],siz[N],top[N],tid[N],tot,son[N],deep[N],w1[N],w2[N],atv[N];
void dfs1(int x)
{
deep[x]=deep[fa[x]]+1; siz[x]++; int y,tmp=0;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa[x])
{
fa[y=to[i]]=x; atv[id[i]]=y; w1[y]=data[i];
dfs1(y); siz[x]+=siz[y];
if(siz[y]>tmp) tmp=siz[y],son[x]=y;
}
}
void dfs2(int x,int anc)
{
tid[x]=++tot; top[x]=anc; w2[tot]=w1[x];
if(son[x]) dfs2(son[x],anc);
for(int i=head[x];i;i=nxt[i])
if(to[i]!=son[x]&&to[i]!=fa[x])
dfs2(to[i],to[i]);
}
bool la[N<<2];
int sum[N<<2],mx[N<<2],mi[N<<2];
void pushup(int pos)
{
sum[pos]=sum[pos<<1]+sum[pos<<1|1];
mx[pos]=max(mx[pos<<1],mx[pos<<1|1]);
mi[pos]=min(mi[pos<<1],mi[pos<<1|1]);
}
void pushdown(int pos)
{
if(!la[pos]) return ;
sum[pos<<1]*=-1; swap(mi[pos<<1],mx[pos<<1]); mx[pos<<1]*=-1; mi[pos<<1]*=-1; la[pos<<1]^=1;
sum[pos<<1|1]*=-1; swap(mi[pos<<1|1],mx[pos<<1|1]); mx[pos<<1|1]*=-1; mi[pos<<1|1]*=-1; la[pos<<1|1]^=1;
la[pos]=0;
}
void build(int pos,int l,int r)
{
if(l==r) {sum[pos]=mx[pos]=mi[pos]=w2[l]; return;}
int mid=l+r>>1; build(pos<<1,l,mid); build(pos<<1|1,mid+1,r);
pushup(pos);
}
void fix_v(int pos,int l,int r,int x,int y)
{
if(l==r){mx[pos]=mi[pos]=sum[pos]=y; return;}
int mid=l+r>>1; pushdown(pos);
if(x<=mid) fix_v(pos<<1,l,mid,x,y);
else fix_v(pos<<1|1,mid+1,r,x,y);
pushup(pos);
}
void fix_e(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) {sum[pos]*=-1; swap(mx[pos],mi[pos]); mx[pos]*=-1; mi[pos]*=-1; la[pos]^=1; return ;}
int mid=l+r>>1; pushdown(pos);
if(y<=mid) fix_e(pos<<1,l,mid,x,y);
else if(x>mid) fix_e(pos<<1|1,mid+1,r,x,y);
else fix_e(pos<<1,l,mid,x,y),fix_e(pos<<1|1,mid+1,r,x,y);
pushup(pos);
}
int q_sum(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return sum[pos];
int mid=l+r>>1,re; pushdown(pos);
if(y<=mid) re=q_sum(pos<<1,l,mid,x,y);
else if(x>mid) re=q_sum(pos<<1|1,mid+1,r,x,y);
else re=q_sum(pos<<1,l,mid,x,y)+q_sum(pos<<1|1,mid+1,r,x,y);
pushup(pos); return re;
}
int q_max(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return mx[pos];
int mid=l+r>>1,re; pushdown(pos);
if(y<=mid) re=q_max(pos<<1,l,mid,x,y);
else if(x>mid) re=q_max(pos<<1|1,mid+1,r,x,y);
else re=max(q_max(pos<<1,l,mid,x,y),q_max(pos<<1|1,mid+1,r,x,y));
pushup(pos); return re;
}
int q_min(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return mi[pos];
int mid=l+r>>1,re; pushdown(pos);
if(y<=mid) re=q_min(pos<<1,l,mid,x,y);
else if(x>mid) re=q_min(pos<<1|1,mid+1,r,x,y);
else re=min(q_min(pos<<1,l,mid,x,y),q_min(pos<<1|1,mid+1,r,x,y));
pushup(pos); return re;
}
void Fix_v()
{
int x,y; scanf("%d%d",&x,&y);
fix_v(1,1,n,tid[atv[x]],y);
}
void Fix_e()
{
int x,y; scanf("%d%d",&x,&y); x++,y++;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
fix_e(1,1,n,tid[top[x]],tid[x]); x=fa[top[x]];
}
if(x==y) return ;
if(deep[x]>deep[y]) swap(x,y);
fix_e(1,1,n,tid[x]+1,tid[y]);
}
void Q_sum()
{
int ans=0,x,y; scanf("%d%d",&x,&y); x++,y++;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans+=q_sum(1,1,n,tid[top[x]],tid[x]); x=fa[top[x]];
}
if(x==y){printf("%d\n",ans); return ;}
if(deep[x]>deep[y]) swap(x,y);
ans+=q_sum(1,1,n,tid[x]+1,tid[y]);
printf("%d\n",ans); return ;
}
void Q_max()
{
int ans=-1<<30,x,y; scanf("%d%d",&x,&y); x++,y++;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans=max(ans,q_max(1,1,n,tid[top[x]],tid[x])); x=fa[top[x]];
}
if(x==y){printf("%d\n",ans); return ;}
if(deep[x]>deep[y]) swap(x,y);
ans=max(ans,q_max(1,1,n,tid[x]+1,tid[y]));
printf("%d\n",ans); return ;
}
void Q_min()
{
int ans=1<<30,x,y; scanf("%d%d",&x,&y); x++,y++;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans=min(ans,q_min(1,1,n,tid[top[x]],tid[x])); x=fa[top[x]];
}
if(x==y){printf("%d\n",ans); return ;}
if(deep[x]>deep[y]) swap(x,y);
ans=min(ans,q_min(1,1,n,tid[x]+1,tid[y]));
printf("%d\n",ans); return ;
}
int main()
{
scanf("%d",&n); int x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z); x++,y++;
add(x,y,z,i); add(y,x,z,i);
}
dfs1(1); dfs2(1,1); build(1,1,n);
scanf("%d",&m);
while(m--)
{
scanf("%s",st);
if(st[0]=='C') Fix_v();
else if(st[0]=='N') Fix_e();
else if(st[0]=='S') Q_sum();
else if(st[1]=='A') Q_max();
else Q_min();
}
return 0;
}