E. Mahmoud and a xor trip

鏈接：

http://codeforces.com/contest/766/problem/E

題意：

給定一顆n節(jié)點(diǎn)的樹(shù)以及每個(gè)節(jié)點(diǎn)的權(quán)值，另dis(u,v)表示節(jié)點(diǎn)u到v路徑上的異或和，求不大于i的節(jié)點(diǎn)與i組成的有序?qū)Φ木嚯x的和（1<=i<=n）。

題解：

位運(yùn)算的話大多可以想到按位拆分，統(tǒng)計(jì)每一位對(duì)答案的貢獻(xiàn)，因?yàn)槊恳晃坏倪\(yùn)算都是獨(dú)立的。所以按位枚舉，假設(shè)當(dāng)前是第b位，則dp[x][0]表示以x為根節(jié)點(diǎn)的異或值為0的路徑的數(shù)量，dp[x][1]也是如此定義。

代碼：

1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <algorithm> 5 6 using namespace std; 7 typedef long long LL; 8 const int N = 1e5 + 10; 9 LL dp[N][2], a[N]; 10 LL ans = 0; 11 vector<int> G[N]; 12 13 void dfs(int x, int fa, int bit) 14 { 15 LL q = 0; 16 int b = (a[x] >> bit) & 1;//取得當(dāng)前的a[x]在第bit位是0還是1， 17 dp[x][b] = 1;//初始化 18 dp[x][b ^ 1] = 0;//初始化 19 for (int i = 0; i<G[x].size(); i++){ 20 int v = G[x][i]; 21 if (v == fa)continue; 22 dfs(v, x, bit); 23 q += dp[x][0] * dp[v][1] + dp[x][1] * dp[v][0];//統(tǒng)計(jì)子節(jié)點(diǎn)到x的路徑上異或和，只需算1^0與0^1即可。 24 dp[x][b ^ 0] += dp[v][0];//更新異或操作后的狀態(tài)值。 25 dp[x][b ^ 1] += dp[v][1];//更新異或操作后的狀態(tài)值。 26 } 27 ans += (q << bit);//更新答案。 28 } 29 int main() 30 { 31 int n, u, v; 32 cin >> n; 33 for (int i = 1; i <= n; i++){ 34 cin >> a[i]; 35 ans += a[i]; 36 } 37 for (int i = 0; i<n - 1; i++){ 38 cin >> u >> v; 39 G[u].push_back(v); 40 G[v].push_back(u); 41 } 42 for (int i = 0; i <= 20; i++)//由于權(quán)值最大為1e6，所以其實(shí)枚舉到20位就足夠了。 43 dfs(1, 0, i); 44 cout << ans << endl; 45 return 0; 46 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/baocong/p/6394398.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #396 (Div. 2) E. Mahmoud and a xor trip 二进制拆位+树型dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。