题目

题目描述

输入格式

输出格式

样例

样例输入

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

样例输出

1
3

题解

SP375的变体，树链剖分好题~~一个lazy标志传递错误让我调了半天……~~
先把边权化为点权，建一张新图
对这张新图跑树链剖分，建一棵线段树来维护区间最大和最小值（正常是只需要最大值，但是因为要去相反数，所以需要维护最小值）
对于$3$个操作：

修改单边权：直接单点修改就可以了
路径取反：划分一下重链，直接区间修改，最大值和最小值取反后交换就好了
路径查询：划分重链，直接区间查询最大值

附上代码：

#include<iostream>
#include<cstdio>
using namespace std;
#define l(X) t[X].l
#define r(X) t[X].r
#define d(X) t[X].max
#define x(X) t[X].min
#define a(X) t[X].add
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);
        }
    }
}