A tree is a connected graph without cycles. You are given a rooted tree with nn nodes, labeled from 1 to n1ton. The tree is rooted at node 11. The parent of the ii-th node is f_{a_i}fai. The edge weight between the ii-th node and f_{a_i}fai is w_iwi
E(u, v)E(u,v) is a set of all the nodes through a path which is from uu to vv, including uu and vv. For example,E(5,3) = \{5, 2, 1, 3\}, E(4,6) = \{4, 3, 6\}, E(2,5) = \{2,5\}E(5,3)={5,2,1,3},E(4,6)={4,3,6},E(2,5)={2,5}
X(u, v)X(u,v) represents the XOR of all edge weights on the path from uu to vvFor example, in the case given above,
X(1,5) = 1X(1,5)=1 xorxor 1=01=0,X(4,6) = 1X(4,6)=1 xorxor 3=23=2,X(2,5) = 1X(2,5)=1,X(3,5) = 2X(3,5)=2 xorxor 11 xorxor 11 =2=2You need to calculate the answer to the following formula:
\displaystyle\sum_{u=1}^n \displaystyle\sum_{v=1}^n \displaystyle\sum_{u' \in E(u,v)} \displaystyle\sum_{v' \in E(u,v)} [u < v][ u' < v'][X(u',v')=0]u=1∑nv=1∑nu′∈E(u,v)∑v′∈E(u,v)∑[u<v][u′<v′][X(u′,v′)=0]
The answer modulo 10000000071000000007
XOR is equivalent to '^' in c / c++ / java / python. If both bits in the compared position of the bit patterns are 00 or 11, the bit in the resulting bit pattern is 00, otherwise 11.Each test file contains a single test case. In each test file:
The first line contains one integer n(1 \le n \le 10^5)n(1≤n≤105) — the number of nodes in the tree.
Then n - 1n−1 lines follow. ii-th line contains two integers f_{a_i}(1 \le f_{a_i} < i)fai(1≤fai<i), w_i(0 \le w_i \le 10^{18})wi(0≤wi≤1018) —The parent of the ii-th node and the edge weight between the ii-th node and f_{a_i} (ifai(i start from 2)2).
Print a single integer — the answer of this problem, modulo 10000000071000000007.
样例输入1复制
2 12样例输出1复制
0样例输入2复制
5 1 0 2 0 3 0 4 0样例输出2复制
35
分析：计算贡献，对于任意两个点，如果这两个点之间的边异或为0，那么
（1）如果这两个点其中一个是另一个的祖先，设v是u的祖先，x是与u在同一条链上的v的儿子，贡献=son(u)*(n-son(x)）
（2）否则贡献=son(u)*son(v)
然后记录根到点的异或值，如果两个点到根的异或值相同的话，这两个点就会产生贡献，记录异或值的size，直接计数就可以了。
#include "bits/stdc++.h" using namespace std; const int mod = 1e9 + 7; struct node { long long u, w; }; int num[100004]; vector<node> v[100004]; void dfs1(int u) { for (int i = 0; i < v[u].size(); ++i) { dfs1(v[u][i].u); num[u] += num[v[u][i].u] + 1; } } unordered_map<long long, long long> mp; unordered_map<long long, long long> mp1;//不同链 unordered_map<long long, long long> mp2;//同链 long long ans = 0; int n; void dfs2(int u, long long xo) { ans = (ans + mp1[xo] * (num[u] + 1) % mod) % mod; ans = (ans + mp2[xo] * (num[u] + 1) % mod) % mod; mp2[xo] += (n - num[u]); mp2[xo] %= mod; for (int i = 0; i < v[u].size(); ++i) { mp2[xo] = (mp2[xo] + num[u] - num[v[u][i].u] - 1) % mod; dfs2(v[u][i].u, xo ^ v[u][i].w); mp2[xo] = (mp2[xo] - num[u] + num[v[u][i].u] + 1 + mod) % mod; } mp2[xo] = (mp2[xo] - (n - num[u]) + mod) % mod; if (mp2[xo] == 0)mp2.erase(xo); mp1[xo] = (mp1[xo] + num[u] + 1) % mod; } int main() { scanf("%d", &n); long long u, w; for (int i = 2; i <= n; ++i) { scanf("%lld%lld", &u, &w); v[u].push_back({i, w}); } dfs1(1); dfs2(1, 0); cout << ans << endl; } /* * 6 1 1 1 2 3 1 2 1 3 3 6 1 0 1 0 3 0 2 0 3 0 */
