本文共 1317 字，大约阅读时间需要 4 分钟。
题意：给定一颗n节点的树以及每个节点的权值，另dis(u,v)表示节点u到v路径上的异或和，求不大于i的节点与i组成的有序对的距离的和（1<=i<=n）。
思路：位运算的话大多可以想到按位拆分，统计每一位对答案的贡献，因为每一位的运算都是独立的。所以按位枚举，假设当前是第b位，则dp[x][0]表示以x为根节点的异或值为0的路径的数量，dp[x][1]也是如此定义。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #define x first17 #define y second18 #define pb push_back19 #define mp make_pair20 #define lson l,m,rt*221 #define rson m+1,r,rt*2+122 #define mt(A,B) memset(A,B,sizeof(A))23 #define mod 100000000724 using namespace std;25 typedef long long LL;26 const double PI = acos(-1);27 const int N=1e5+10;28 const int inf = 0x3f3f3f3f;29 const LL INF=0x3f3f3f3f3f3f3f3fLL;30 LL dp[N][2],a[N];31 LL ans=0;32 vector G[N];33 LL dfs(int x,int fa,int bit)34 {35 LL q=0;36 int b=(a[x]>>bit)&1;//取得当前的a[x]在第bit位是0还是1，37 dp[x][b]=1;//初始化38 dp[x][b^1]=0;//初始化39 for(int i=0;i >n;59 for(int i=1;i<=n;i++)60 {61 cin>>a[i];62 ans+=a[i];63 }64 for(int i=0;i >u>>v;67 G[u].pb(v);68 G[v].pb(u);69 }70 for(int i=0;i<=20;i++)//由于权值最大为1e6，所以其实枚举到20位就足够了。71 {72 dfs(1,0,i);73 }74 cout< <
转载于:https://www.cnblogs.com/27sx/p/6382800.html
