题目链接：https://cn.vjudge.net/contest/279350#problem/D
题目大意：操作，单点查询，区间取反，询问区间最大值。
AC代码：
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
#include<stdio.h>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
# define inf 0x3f3f3f3f
# define ll long long
# define lson l,m,rt<<
# define rson m+,r,rt<<|
const int maxn = 3e5+;
int sto[maxn],head[maxn],edgnum,dfsnum,depth[maxn];
int son[maxn],father[maxn],Size[maxn],ord[maxn],cost[maxn],top[maxn];
int maxtree[maxn<<],mintree[maxn<<],maxx,lazy[maxn<<];
struct node
{
int fr;
int to;
int nex;
int cost;
} edge[maxn],po[maxn];
void addedge(int fr,int to)
{
edge[edgnum].fr=fr;
edge[edgnum].to=to;
edge[edgnum].nex=head[fr];
head[fr]=edgnum++;
}
void dfs1(int fr,int rt,int dep)
{
father[fr]=rt;
Size[fr]=;
son[fr]=-;
depth[fr]=dep;
for(int i=head[fr]; i!=-; i=edge[i].nex)
{
int to=edge[i].to;
if(to==rt)
continue;
dfs1(to,fr,dep+);
Size[fr]+=Size[to];
if(son[to]==-||(Size[son[fr]]<Size[to]))
{
son[fr]=to;
}
}
}
void dfs2(int fr,int rt)
{
ord[fr]=++dfsnum;
cost[ord[fr]]=sto[fr];
top[fr]=rt;
if(son[fr]!=-)
dfs2(son[fr],rt);
for(int i=head[fr]; i!=-; i=edge[i].nex)
{
int u=edge[i].to;
if(son[fr]!=u&&father[fr]!=u)
{
dfs2(u,u);
}
}
}
void up(int rt)
{
maxtree[rt]=max(maxtree[rt<<],maxtree[rt<<|]);
mintree[rt]=min(mintree[rt<<],mintree[rt<<|]);
}
void buildtree(int l,int r,int rt)
{
if(l==r)
{
maxtree[rt]=sto[l];
mintree[rt]=sto[l];
lazy[rt]++;
return ;
}
int m=(l+r)>>;
buildtree(lson);
buildtree(rson);
up(rt);
}
void change(int rt)
{
int tmp=mintree[rt];
mintree[rt]=-maxtree[rt];
maxtree[rt]=-tmp;
}
void down(int rt)
{
if(!lazy[rt])
return ;
lazy[rt<<]^=;
lazy[rt<<|]^=;
change(rt<<);
change(rt<<|);
lazy[rt]^=;
}
void query(int l,int r,int rt,int L,int R)
{
if(L<=l&&R>=r)
{
maxx=max(maxx,maxtree[rt]);
return ;
}
down(rt);
int m=(l+r)>>;
if(L<=m)
query(lson,L,R);
if(R>m)
query(rson,L,R);
up(rt);
}
void update1(int l,int r,int rt,int pos,int p)
{
if(l==r)
{
maxtree[rt]=p;
mintree[rt]=p;
return ;
}
down(rt);
int m=(l+r)>>;
if(pos<=m)
update1(lson,pos,p);
if(pos>m)
update1(rson,pos,p);
up(rt);
}
void update2(int l,int r,int rt,int L,int R)
{
if(L<=l&&R>=r)
{
change(rt);
lazy[rt]^=;
return ;
}
down(rt);
int m=(l+r)>>;
if(L<=m)
update2(lson,L,R);
if(R>m)
update2(rson,L,R);
up(rt);
}
void Query(int n,int x,int y)
{
maxx=-inf;
int tx=top[x],ty=top[y];
while(tx!=ty)
{
if(depth[tx]<depth[ty])
{
swap(tx,ty);
swap(x,y);
}
query(,n,,ord[tx],ord[x]);
x=father[tx],tx=top[x];
}
if(depth[x]<depth[y])
{
swap(x,y);
}
query(,n,,ord[y]+,ord[x]);
}
void Update(int n,int x,int y)
{
int tx=top[x],ty=top[y];
while(tx!=ty)
{
if(depth[tx]<depth[ty])
{
swap(tx,ty);
swap(x,y);
}
update2(,n,,ord[tx],ord[x]);
x=father[tx],tx=top[x];
}
if(depth[x]<depth[y])
{
swap(x,y);
}
update2(,n,,ord[y]+,ord[x]);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
dfsnum=edgnum=;
int n,q,s;
scanf("%d",&n);
int t1,t2,t3;
memset(maxtree,,sizeof(maxtree));
memset(mintree,,sizeof(mintree));
memset(lazy,,sizeof(lazy));
memset(head,-,sizeof(head));
for(int i=; i<=n-; i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
addedge(t1,t2);
addedge(t2,t1);
po[i].fr=t1;
po[i].to=t2;
po[i].cost=t3;
}
dfs1(,-,);
dfs2(,);
for(int i=; i<=n-; i++)
{
t1=depth[po[i].fr];
t2=depth[po[i].to];
if(t1>t2)
{
swap(po[i].fr,po[i].to);
}
update1(,n,,ord[po[i].to],po[i].cost);
}
char str[];
while(~scanf("%s",str))
{
if(str[]=='D')
break;
else if(str[]=='Q')
{
scanf("%d %d",&t1,&t2);
Query(n,t1,t2);
printf("%d\n",maxx);
}
else if(str[]=='C')
{
scanf("%d %d",&t1,&t2);
update1(,n,,ord[po[t1].to],t2);
}
else if(str[]=='N')
{
scanf("%d %d",&t1,&t2);
Update(n,t1,t2);
}
}
}
return ;
}