Question

杭州电子科技大学2023新生赛 E 树

给定一颗包含 \(n\) 个节点的带边权的树，定义 \(xordist(u,v)\) 为节点 \(u\) 到 \(v\) 的简单路径上所有边权值的异或和

有 \(q\) 次询问，每次给出 l r x 求 \(\sum_{i=l}^r xordist(i,x)\) 的值

Solution

考试的时候脑子坏了

对于一条树上的路径 \(xordist(i,x)\) 可以进行分解

\(xordist(i,x)=xordist(c,i)\oplus xordist(c,x)\) ，其中 \(c\) 为任意常数，这个结论在树上和在数轴上都是成立的

方便起见我们定 \(c=1\)，那么我们可以把 \(\sum_{i=l}^r xordist(i,x)\) 拆开

\[\sum_{i=l}^r xordist(i,x)=\sum_{i=l}^r xordist(1,i)\oplus xordist(1,x) \]

此时枚举 \(l\sim r\) 还是会超时，考虑每一位看，预处理出每一位 \(\sum_1^i xordist(1,i)\) ，那么我们就能通过前缀和快速计算出 \(l\sim r\) 在每一位上有几个 \(0\) 几个 \(1\)，然后对应 \(xordist(1,x)\) 来累计 \(ans\)

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
struct Edge{
    int from,to,w;
    Edge(int u,int v,int w):from(u),to(v),w(w){}
};
vector<Edge> edges;
struct Bit{
    int c[32];
    Bit(){memset(c,0,sizeof(c));}
    Bit(int x){
        memset(c,0,sizeof(c));
        for(int i=0;i<=31;i++) c[i]=x>>i&1;
    }
    void Get(int x){
        for(int i=0;i<=31;i++){
            c[i]=x>>i&1;
        }
    }
};

int n,Q;
vector<int> F;
vector<vector<int> > G;
vector<Bit> s;

void dfs(int x,int fa=0){
    for(int i=0;i<G[x].size();i++){
        auto& e=edges[G[x][i]];
        if(e.to==fa) continue;
        F[e.to]=F[x]^e.w;
        dfs(e.to,x);
    }
}

void solve(){
    n=read();

    G.assign(n+1,vector<int>()); s.assign(n+1,Bit());F.assign(n+1,0); edges.clear();
    
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        edges.push_back(Edge(u,v,w));
        G[u].push_back(edges.size()-1);
        edges.push_back(Edge(v,u,w));
        G[v].push_back(edges.size()-1);
    }

    dfs(1);

    for(int i=1;i<=n;i++){
        Bit now(F[i]); 
        for(int j=0;j<=31;j++){
            s[i].c[j]=s[i-1].c[j]+now.c[j];
        }
    }

    Q=read();
    while(Q--){
        int l=read(),r=read(),x=read();
        Bit now(F[x]);
        LL ans=0;
        for(int i=0;i<=31;i++){
            if(now.c[i]==0)
                ans+=(LL)(s[r].c[i]-s[l-1].c[i])*(1<<i);
            else
                ans+=(LL)((r-l+1)-(s[r].c[i]-s[l-1].c[i]))*(1<<i);
        }
        printf("%lld\n",ans);
    }
}

int main(){
    int T=read();
    while(T--) solve();
}