哈尔滨理工大学2016新生赛J题

给出一棵有N个节点(2 <= N <= 500000)和N-1条边的树，每条边拥有一个长度L(1 <= L <= 500000)。

定义：

（1） path(u, v) = 顶点u和v之间的最短路。

（2） xor-distance(u, v) = ⊕e∈path(u,v)length(e), ⊕代表异或操作。

请计算出有多少对点的xor-distance的值等于K（0 <= K <= 500000）。（v != u 并且 pair(u,v) = pair(v,u)）。

第一行是一个整数T，表示有T组测试数据。

接下来T组测试数据，每组测试数据开始为两个正整数N，K，接下来N-1行每行包含三个整数u,v,L(0 <= u,v <= N-1),代表树中存在一条顶点为u，v，边长为L的边。

每组一行，输出点对的个数。

4 1

0 1 1

1 2 3

2 3 2

3 0

0 1 7

0 2 7

本题乍看可以用树的划分等比较麻烦的方法去做，但实际上考虑到异或的特殊性质，不需要用到这些方法的方法。

首先回想我们是如何计算树上两点之间的距离的，先分别求出根到这两点之间的距离，记为l1, l2，根到这两点的最近公共祖先的距离为lc.那么这两点距离就是（l1 ＋ l2）- (lc + lc).

然后回到原问题，我们要求的是两点之间的异或距离，同样先求出根到这两点的异或距离，记为x1, x2，根到这两点最近公共祖先距离为xc，那么这两点的异或距离就是x1⊕x2⊕xc⊕xc,所以异或距离就是x1⊕x2，那么我们只需要直到有多少点对，满足根分别到他们的异或距离异或后等于K。

于是我们把问题转换为一个很简单的问题，给出N个数字，问有多少对数字异或后等于K，枚举这些数字，然后统计枚举到的数字和K值出现的次数，加到答案里，问题就解决了。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <assert.h>
 5 typedef long long LL;
 6 const int MAXN = 500007;
 7 
 8 struct Edge {
 9     int to, w;
10     Edge* next;
11 };
12 
13 Edge edges[MAXN * 2], * g[MAXN];
14 int nEdge;
15 int open[MAXN];
16 int a[MAXN];
17 bool vst[MAXN];
18 int hash[MAXN * 2];
19 int N, K;
20 
21 inline void addEdge(int x, int y, int w) {
22     Edge* p = &edges[nEdge++];
23     p->to = y;
24     p->w = w;
25     p->next = g[x];
26     g[x] = p;
27 }
28 
29 void bfs() {
30     int i, j, x, m = 0;
31     Edge* p;
32 
33     memset(vst, false, N);
34     open[m++] = 0;
35     vst[0] = true;
36     for (i = 0; i < m; ++i) {
37         x = open[i];
38         for (p = g[x]; p; p = p->next) {
39             if (!vst[p->to]) {
40                 a[p->to] = (a[x] ^ p->w);
41                 vst[p->to] = true;
42                 open[m++] = p->to;
43             }
44         }
45     }
46     for (i = 0; i < N; ++i) {
47         ++hash[a[i]];
48         assert(vst[i] == true);
49     }
50 }
51 
52 void input() {
53     int i, x, y, w;
54 
55     scanf("%d%d", &N, &K);
56     assert(2 <= N && N <= 500000);
57     assert(0 <= K && K <= 500000);
58     for (i = 0; i < N; ++i) {
59         g[i] = NULL;
60     }
61     nEdge = 0;
62 
63     for (i = 0; i < N - 1; ++i) {
64         scanf("%d%d%d", &x, &y, &w);
65         assert(0 <= x && x < N);
66         assert(0 <= y && y < N);
67         assert(1 <= w && w <= 500000);
68         addEdge(x, y, w);
69         addEdge(y, x, w);
70     }
71 }
72 
73 void solve() {
74     int i, j;
75     LL ans = 0;
76 
77     bfs();
78     for (i = 0; i < N; ++i) {
79         ans += hash[a[i] ^ K];
80     }
81     if (K == 0) ans -= N;
82     ans /= 2;
83     printf("%I64d
", ans);
84     // clear the hash
85     for (i = 0; i < N; ++i) {
86         hash[a[i]] = 0;
87     }
88 }
89 
90 int main() {
91     int T;
92     scanf("%d", &T);
93     assert(T <= 50);
94     while (T--) {
95         input();
96         solve();
97     }
98     return 0;
99 }