题解：CF1980G Yasya and the Mysterious Tree

· · 题解

duel 被 rnf 打爆了，死因是在这题调了 1h 17min 的 trie /qd

这个询问等价于从树上摘一条以 v 为端点长度不为零的路径下来，然后求将这个路径的总代价异或上 x 后能得到的最大值。

修改由于是对于全局的，改了跟没改似的，直接对于询问的 x 修改即可。多次修改显然也可以异或到一起。

求路径异或和考虑一个树上差分状物，但是你维护出来以后容易发现路径的异或其实等于两个端点到根的路径异或相异或后的值。

证明是容易的，根到 LCA 的段会被计数两次，于是没有贡献。

接下来就是求最大异或了，考虑直接上一个字典树。

挂了，因为你发现当路径长度为偶数时修改并不生效。

然后我们发现深度奇偶性相同的路径长度为偶数，否则是奇数。

于是根据深度奇偶性开两棵 trie，同一棵树内不给修改的效果。

并不能过样例。

核心问题是，我们不能选中自己当另一个端点。

所以我们需要将 v 对应的值从 trie 里删掉，查询完以后再加回去。

这个部分的实现可以通过给节点记录访问个数来进行。

具体的你可以先把 CF706D 过了，唉像我这样从来没写过带删 trie 的糖批现场瞎编于是就调调爆了。

大致就这样。祝通过。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[2][3300005][2],dududu[2];
int sum[2][3300005];
void inset(int s,int op){
    int flc=0;
    for(int i=31;i>=0;i--){
        int x=(s>>i)&1;
        if(!f[op][flc][x])f[op][flc][x]=++dududu[op];
        flc=f[op][flc][x];
        sum[op][flc]++;
    }
}
int find(int s,int op){
    int flc=0,now=0;
    for(int i=31;i>=0;i--){
        int x=(s>>i)&1;
        if(!sum[op][f[op][flc][x^1]]||!f[op][flc][x^1])flc=f[op][flc][x];
        else flc=f[op][flc][x^1],now^=1<<i;
    }
    return now;
}
void del(int s,int op){
    int flc=0;
    for(int i=31;i>=0;i--){
        int x=(s>>i)&1;
        flc=f[op][flc][x];
        sum[op][flc]--;
    }
}
vector<pair<int,int> >ve[200005];
int dp[200005],dep[200005];
void dfs(int x,int fa){
    for(int i=0;i<ve[x].size();i++){
        if(ve[x][i].first==fa)continue;
        dp[ve[x][i].first]=dp[x]^ve[x][i].second;
        dep[ve[x][i].first]=1^dep[x];
        dfs(ve[x][i].first,x);
    }
}
void solve(){
    for(int i=0;i<=dududu[0];i++)
    sum[0][i]=sum[0][i]=f[0][i][0]=f[0][i][1]=0;dududu[0]=0;
    for(int i=0;i<=dududu[1];i++)
    sum[1][i]=sum[1][i]=f[1][i][0]=f[1][i][1]=0;dududu[1]=0;
    int n,m,qwq=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    dp[i]=0,ve[i].clear();
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        ve[u].push_back({v,w});
        ve[v].push_back({u,w});
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
    inset(dp[i],dep[i]);
    while(m--){
        char c;
        cin>>c;
        if(c=='^'){
            int y;
            cin>>y;
            qwq^=y;
        }else{
            int v,x;
            cin>>v>>x;
            del(dp[v],dep[v]);
            cout<<max(find(dp[v]^x^qwq,dep[v]^1),find(dp[v]^x,dep[v]))<<' ';
            inset(dp[v],dep[v]);
        }
    }cout<<'\n';
}
signed main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
// 「来～快感谢本大爷～崇拜本大爷～向本大爷说谢谢～」
// 面对迎面逼近而来的尼洛，莫妮卡不断向后仰，嘴巴开阖不停。
// 「噫、噫～～……谢……唔……啊啊……谢……唔唔唔……啊、啊……」

话说怎么就已经写这么长了，这不是一道极其简单的 *2300 吗 /yiw

一定是解释的太史了，谢罪 /wq