题解：CF1413F Roads and Ramen

· · 题解

题目传送门

题目大意

给出一颗树，每一条边的边权位 0 或 1，一共有 m 次修改，每次对一条边的边权取反，每次修改后求出树上最长的一条路径使得路径异或和为 0。

解题思路

首先有一个非常重要的性质，就是这条最长路径的一个端点一定是这棵树的直径的一端。现在考虑证明。

上图中 AB 是直径如果 AB 满足条件，那么最长路径肯定是 AB。如果 AB 不满足条件，而 CD 是一条合法路径，那我们分类讨论，首先是 CD 与 AB 没有重合的路径，EF 是连接路径 AB 和 CD 的路径。因为 AB 不合法，所以 AE 和 BE 的异或和不同，所以 AF 和 BF 的异或和不同。而因为 CD 满足条件，所以 CF 和 DF 的异或和相同，显然 AF 或 BF 一定可以和 CF 或 DF 组成一条合法路径。容易证明这样组成的路径要比原先的 CD 更长。我们不妨假设 AF 和 DF 可以组成合法路径，因为 AB 是直径，所以 AF 的长度一定不劣于 CF 否则直径则是 BC。所以 AD 的长度一定不劣于 $CD。

现在考虑另一种情况，即 AB 和 CD 有重合的路径 EF。接下来要对 EF 的路径异或和进行分类讨论，我这里只讲一种，另一种同理。假定 EF 的异或和为 0。因为 AB 不合法，说明 AE 和 BF 的路径异或和不同，又因为 CD 合法，所以 CE 和 DF 的路径异或和相同。同理，AE 或 BF 一定可以和 CE 或 DF 组成一条合法路径。假定 AF 可以和 DF 组成一条合法路径，因为 AB 是直径，所以 AE 的长度一定不劣于 CE 否则直径则是 BC。所以 AD 的长度一定不劣于 CD。证毕。

现在考虑如何运用这个性质。现在我们知道了最长路径的一端一定是直径中的一端，所以我们可以想到分别建两颗线段树，一棵是以直径的一端为根，另一棵是以直径的另一端为根。把树上的点用 dfn 序来表示，就可以进行区间操作了，线段树区间 [l,r] 中分别存储这在这些点中到根节点异或和为 0 和 1的最大深度。而最终答案就是区间 [1,n] 中异或和为 0 的最大深度。

考虑修改，修改其实只会对子树中的点有影响，而影响就是交换异或和为 0 和 1 的最大深度。所以我们可以用懒标记维护一下即可。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2010101;
ll n,res,tot,head[N],m,rt1,rt2;
struct tt{ll to,w,next;}e[N];
struct edge{ll u,v,w;}g[N];
void add(ll u,ll v,ll w){e[++tot].to=v,e[tot].w=w,e[tot].next=head[u],head[u]=tot;}
void dfs1(ll u,ll fa,ll dep){
    if(dep>res)res=dep,rt1=u;
    for(int i=head[u];i;i=e[i].next){
        ll v=e[i].to;
        if(v==fa)continue;
        dfs1(v,u,dep+1);
    }
}
void dfs2(ll u,ll fa,ll dep){
    if(dep>res)res=dep,rt2=u;
    for(int i=head[u];i;i=e[i].next){
        ll v=e[i].to;
        if(v==fa)continue;
        dfs2(v,u,dep+1);
    }
}
void get_root(){
    res=0;dfs1(1,0,0);
    res=0;dfs2(rt1,0,0);
}
struct segment_tree{
    ll t[N][2],f[N],dfn[N],rnk[N],dep[N],col[N],lx[N],rx[N],laz[N],top;
    void dfs(ll u,ll fa){
        dfn[u]=++top;
        rnk[top]=u;
        f[u]=fa;
        lx[u]=top;
        for(int i=head[u];i;i=e[i].next){
            ll v=e[i].to;
            if(v==fa)continue;
            dep[v]=dep[u]+1;
            col[v]=col[u]^e[i].w;
            dfs(v,u);
        }
        rx[u]=top;
    }
    void pushup(ll p){
        t[p][0]=max(t[p<<1][0],t[p<<1|1][0]);
        t[p][1]=max(t[p<<1][1],t[p<<1|1][1]);
    }
    void pushdown(ll p){
        if(laz[p]){
            swap(t[p<<1][0],t[p<<1][1]);
            swap(t[p<<1|1][0],t[p<<1|1][1]);
            laz[p<<1]^=1,laz[p<<1|1]^=1;
            laz[p]=0;
        }
    }
    void build(ll p,ll l,ll r){
        if(l==r){
            if(col[rnk[l]])t[p][1]=dep[rnk[l]];
            else t[p][0]=dep[rnk[l]];
            return;
        }
        ll mid=(l+r)>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        pushup(p);
    }
    void update(ll p,ll l,ll r,ll x,ll y){
        if(y<l||r<x)return;
        if(x<=l&&r<=y){
            swap(t[p][0],t[p][1]);
            laz[p]^=1;
            return;
        }
        ll mid=(l+r)>>1;
        pushdown(p);
        if(x<=mid)update(p<<1,l,mid,x,y);
        if(y>mid)update(p<<1|1,mid+1,r,x,y);
        pushup(p);
    }
    ll query(){return t[1][0];}
    void check(ll x,ll y){
        if(f[x]==y)update(1,1,n,lx[x],rx[x]);
        else update(1,1,n,lx[y],rx[y]);
    }
}T[2];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        g[i].u=u,g[i].v=v,g[i].w=w;
        add(u,v,w);
        add(v,u,w);
    }
    get_root();
    T[0].dfs(rt1,0);T[0].build(1,1,n);
    T[1].dfs(rt2,0);T[1].build(1,1,n);
    cin>>m;
    while(m--){
        ll id;
        cin>>id;
        T[0].check(g[id].u,g[id].v);
        T[1].check(g[id].u,g[id].v);
        cout<<max(T[0].query(),T[1].query())<<'\n';
    }
    return 0;
}