题目描述
给定一个N个结点的无向树，树中的结点按照1...N编号，树中的边按照1...N − 1编号，每条边都赋予一个权值。你需要编写程序支持以下三种操作：
1. CHANGE i v：将i号边的权值改为v。
2. NEGATE a b：将结点a到结点b路径上每条边权值取相反数。例如NEGATE(-3)=3,
NEGATE(3)=-3。
3. QUERY a b：返回结点a到结点b路径上权值最大边的权值。
输入
第一行为N(N ≤ 105)，代表树中结点的个数。
接下来N − 1行，每行三个整数x y w表示有一条连接结点x和y的边，权值为w。
接下来若干行代表了三种操作。操作的格式见问题描述。遇到一行“DONE”时结束。
不会超过105个操作（不包含DONE）。
输入数据中有30%的数据，满足N ≤ 100。
输出
对于每个QUERY操作，输出一行，代表最大的权值。
样例输入
3 1 2 1 2 3 2 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE
样例输出
1 3
题解：
树链剖分水题，但小测的时候打错了，发个博客以泄愤。
关键：线段树中不仅维护最大值又要维护最小值，然后取反就相当于swap(最小值，最大值).
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ls (node<<1)
#define rs (node<<1|1)
using namespace std;
const int N=,INF=;
int n;
int gi()
{
int str=,f=;char ch=getchar();
while(ch>'' || ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<='')str=str*+ch-'',ch=getchar();
return str*f;
}
int num=,head[N],haha[N];char s[];
struct TT{
int minn,maxn;
}Tree[N*];
int mark[N*];
struct Lin{
int next,to,dis;
}a[N*];
struct Edge{
int x,y,z;
}e[N];
void updata(int node){
Tree[node].maxn=Tree[ls].maxn>Tree[rs].maxn?Tree[ls].maxn:Tree[rs].maxn;
Tree[node].minn=Tree[ls].minn<Tree[rs].minn?Tree[ls].minn:Tree[rs].minn;
}
void init(int x,int y,int z)
{
a[++num].next=head[x];
a[num].to=y;
a[num].dis=z;
head[x]=num;
a[++num].next=head[y];
a[num].to=x;
a[num].dis=z;
head[y]=num;
}
int top[N],dep[N],id[N],son[N],fa[N],size[N],ids=;
void dfs1(int x)
{
int u;
size[x]=;
for(int i=head[x];i;i=a[i].next)
{
u=a[i].to;
if(dep[u])continue;
dep[u]=dep[x]+;fa[u]=x;
dfs1(u);
size[x]+=size[u];if(size[u]>size[son[x]])son[x]=u;
}
}
void dfs2(int x,int tp)
{
id[x]=++ids;top[x]=tp;
if(son[x])dfs2(son[x],tp);
int u;
for(int i=head[x];i;i=a[i].next){
u=a[i].to;
if(u==son[x] || u==fa[x])continue;
dfs2(u,u);
}
}
void build(int l,int r,int node)
{
mark[node]=;
if(l==r){Tree[node].maxn=Tree[node].minn=haha[l];return ;}
int mid=(l+r)>>;
build(l,mid,ls);
build(mid+,r,rs);
updata(node);
}
void pushdown(int node)
{
if(!mark[node])return ;
mark[ls]^=;mark[rs]^=;
swap(Tree[rs].maxn,Tree[rs].minn);Tree[ls].maxn*=-;Tree[ls].minn*=-;
swap(Tree[ls].maxn,Tree[ls].minn);Tree[rs].maxn*=-;Tree[rs].minn*=-;
mark[node]=;
}
void cg(int l,int r,int node,int sa,int se,int toit)
{
if(l>se || r<sa)return ;
if(sa<=l && r<=se){
if(toit==INF){mark[node]^=;swap(Tree[node].maxn,Tree[node].minn);Tree[node].maxn*=-;Tree[node].minn*=-;}
else {Tree[node].maxn=Tree[node].minn=toit;}
return ;
}
pushdown(node);
int mid=(l+r)>>;
cg(l,mid,ls,sa,se,toit);
cg(mid+,r,rs,sa,se,toit);
updata(node);
}
void Change(int x,int y){
cg(,n,,id[e[x].x],id[e[x].x],y);
}
void Negdata(int x,int y)
{
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
cg(,n,,id[top[x]],id[x],INF);
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
cg(,n,,id[y]+,id[x],INF);
return ;
}
int getsum(int l,int r,int node,int sa,int se)
{
if(l>se || r<sa)return -INF;
if(sa<=l && r<=se)return Tree[node].maxn;
pushdown(node);
int mid=(l+r)>>;
return max(getsum(l,mid,ls,sa,se),getsum(mid+,r,rs,sa,se));
updata(node);
}
int Ask(int x,int y)
{
int ans=-INF,tmp;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
tmp=getsum(,n,,id[top[x]],id[x]);
if(tmp>ans)ans=tmp;
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
tmp=getsum(,n,,id[y]+,id[x]);
return max(tmp,ans);
}
int main()
{
n=gi();
int x,y;
for(int i=;i<n;i++){
e[i].x=gi();e[i].y=gi();e[i].z=gi();
init(e[i].x,e[i].y,e[i].z);
}
dep[]=;dfs1();dfs2(,);fa[]=;haha[]=-INF;
for(int i=;i<n;i++){
x=e[i].x;y=e[i].y;
if(dep[x]<dep[y])swap(x,y),swap(e[i].x,e[i].y);
haha[id[x]]=e[i].z;
}
build(,n,);
while()
{
scanf("%s%d%d",s,&x,&y);
if(s[]=='D')break;
if(s[]=='C')Change(x,y);
else if(s[]=='N')Negdata(x,y);
else if(s[]=='Q')printf("%d\n",Ask(x,y));
}
return ;
}