Codeforces Round #396 (Div. 2) E. Mahmoud and a xor trip（树形dp+二进制按位拆分）

女爷i 2022-07-12 08:41 154阅读 0赞

[CF E][]

题解：给你一棵n个节点的树以及每个节点的权值，点权。dis(u,v)表示节点u到v路径上的异或和，求不大于i的节点与i组成的有序对的距离的和（1<=i<=n）。

题解：树形dp。因为XOR时每一位的操作都是独立的，所以我们可以考虑将这些数的二进制按位拆分考虑。枚举二进制的每一位对，统计对答案的贡献。考虑当前的根节点为cur，那么：

dp\[cur\]\[0\]表示以cur为根节点的异或值为0的路径的数量。  
dp\[cur\]\[1\]表示以cur为根节点的异或值为1的路径的数量 。

代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1e5 + 10;
    ll dp[N][2];
    ll a[N];
    ll ans = 0;
    vector<int> G[N];
    void dfs(int cur, int fa, int bit)
    {
        ll res = 0;
        int b = (a[cur] >> bit) & 1;//取得当前的a[cur]在第bit位是0还是1
        //这里好巧妙啊... 
        dp[cur][b] = 1;//初始化
        dp[cur][b ^ 1] = 0;//初始化
        
        for(auto v:G[cur]){
        	if(v!=fa){
        		dfs(v, cur, bit);
            	res += dp[cur][0] * dp[v][1] + dp[cur][1] * dp[v][0];//统计子节点到cur的路径上异或和，只需算1^0与0^1即可 
            	dp[cur][b ^ 0] += dp[v][0];//更新异或操作后的状态值
            	dp[cur][b ^ 1] += dp[v][1];//更新异或操作后的状态值
    		}
    	}	
    	/*
        for (int i = 0; i<G[cur].size(); i++)
    	{
            int v = G[cur][i];
            if (v == fa)continue;
            dfs(v, cur, bit);
            q += dp[cur][0] * dp[v][1] + dp[cur][1] * dp[v][0];
            dp[cur][b ^ 0] += dp[v][0];
            dp[cur][b ^ 1] += dp[v][1];
        }
        */
        ans += (res << bit);//更新答案
    }
    int main()
    {
        int n, u, v;
        cin >> n;
        for (int i = 1; i <= n; i++){
    	    cin >> a[i];
            ans += a[i];
        }
        for (int i = 0; i<n - 1; i++){
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        //由于权值最大为1e6，所以只需要枚举到20位。2^20=1048576 
        for (int i = 0; i <= 20; i++)
            dfs(1, 0, i);
       return 0*printf("%I64d\n",ans);
    }
    /*
    5
    1 2 3 4 5
    1 2
    2 3
    3 4
    3 5
    
    52
    */

[CF E]: http://codeforces.com/contest/766/problem/E