专栏文章

题解：CF1413F Roads and Ramen

hhoko
CF1413F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio1jxt1
此快照首次捕获于
2025/12/02 11:51
3 个月前
此快照最后确认于
2025/12/02 11:51
3 个月前
查看原文

题目传送门

题目大意

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

解题思路

首先有一个非常重要的性质，就是这条最长路径的一个端点一定是这棵树的直径的一端。现在考虑证明。
上图中 ABAB 是直径如果 ABAB 满足条件，那么最长路径肯定是 ABAB。如果 ABAB 不满足条件，而 CDCD 是一条合法路径，那我们分类讨论，首先是 CDCD 与 ABAB 没有重合的路径，EFEF 是连接路径 ABAB 和 CDCD 的路径。因为 ABAB 不合法，所以 AEAE 和 BEBE 的异或和不同，所以 AFAF 和 BFBF 的异或和不同。而因为 CDCD 满足条件，所以 CFCF 和 DFDF 的异或和相同，显然 AFAF 或 BFBF 一定可以和 CFCF 或 DFDF 组成一条合法路径。容易证明这样组成的路径要比原先的 CDCD 更长。我们不妨假设 AFAF 和 DFDF 可以组成合法路径，因为 ABAB 是直径，所以 AFAF 的长度一定不劣于 CFCF 否则直径则是 BCBC。所以 ADAD 的长度一定不劣于 $CD。
现在考虑另一种情况，即 ABAB 和 CDCD 有重合的路径 EFEF。接下来要对 EFEF 的路径异或和进行分类讨论，我这里只讲一种，另一种同理。假定 EFEF 的异或和为 00。因为 ABAB 不合法，说明 AEAE 和 BFBF 的路径异或和不同，又因为 CDCD 合法，所以 CECE 和 DFDF 的路径异或和相同。同理，AEAE 或 BFBF 一定可以和 CECE 或 DFDF 组成一条合法路径。假定 AFAF 可以和 DFDF 组成一条合法路径，因为 ABAB 是直径，所以 AEAE 的长度一定不劣于 CECE 否则直径则是 BCBC。所以 ADAD 的长度一定不劣于 CDCD。证毕。
现在考虑如何运用这个性质。现在我们知道了最长路径的一端一定是直径中的一端，所以我们可以想到分别建两颗线段树，一棵是以直径的一端为根，另一棵是以直径的另一端为根。把树上的点用 dfn 序来表示，就可以进行区间操作了，线段树区间 [l,r][l,r] 中分别存储这在这些点中到根节点异或和为 00 和 11的最大深度。而最终答案就是区间 [1,n][1,n] 中异或和为 00 的最大深度。
考虑修改，修改其实只会对子树中的点有影响，而影响就是交换异或和为 00 和 11 的最大深度。所以我们可以用懒标记维护一下即可。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...