[UVa] 13277 - XOR Path

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13277 - XOR Path 
Source            : UVA Online Judge
Category          : Linear Algebra, Graph Theory
Algorithm         : Fast Walsh-Hadamard transform, dfs 
Verdict           : Accepted

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. #define ll         long long  
6.   
7. static const int maxn = 1e5 + 5;  
8. static const int N    = 1<<16;  
9.   
10. template <typename T> struct FWT  
11. {  
12.       void fwt(T io[], int n)  
13.       {  
14.             for (int d = 1; d < n; d <<= 1)  
15.             {  
16.                   for (int i = 0, m = d<<1; i < n; i += m)  
17.                   {  
18.                         for (int j = 0; j < d; j++)  
19.                         {  
20.                               T x = io[i+j], y = io[i+j+d];  
21.                               io[i+j] = (x+y), io[i+j+d] = (x-y);  // xor  
22.                               //io[i+j] = x+y;                     // and  
23.                               //io[i+j+d] = x+y;                   // or  
24.                         }  
25.                   }  
26.             }  
27.       }  
28.       void ufwt(T io[], int n)  
29.       {  
30.             for (int d = 1; d < n; d <<= 1)  
31.             {  
32.                   for (int i = 0, m = d<<1; i < n; i += m)  
33.                   {  
34.                         for (int j = 0; j < d; j++)  
35.                         {  
36.                               T x = io[i+j], y = io[i+j+d];  
37.                               io[i+j] = (x+y)>>1, io[i+j+d] = (x-y)>>1; // xor  
38.                               //io[i+j] = x-y;                          // and  
39.                               //io[i+j+d] = y-x;                        // or  
40.                         }  
41.                   }  
42.             }  
43.       }  
44.       void convolution(T a[], T b[], int n)  
45.       {  
46.             fwt(a, n);  
47.             fwt(b, n);  
48.             for (int i = 0; i < n; i++) a[i] = a[i] * b[i];  
49.             ufwt(a, n);  
50.       }  
51.       void self_convolution(T a[], int n)  
52.       {  
53.             fwt(a, n);  
54.             for (int i = 0; i < n; i++) a[i] = a[i] * a[i];  
55.             ufwt(a, n);  
56.       }  
57. };  
58.   
59. struct node  
60. {  
61.     int v, w;  
62.     node() {}  
63.     node(int v, int w)  
64.     {  
65.         this->v = v;  
66.         this->w = w;  
67.     }  
68. };  
69.   
70. vector <node> graph[maxn];  
71. FWT <ll> fwt;  
72. ll arr[N+5];  
73.   
74. void dfs(int u = 1, int p = -1, int x = 0)  
75. {  
76.       arr[x]++;  
77.       for (auto &it : graph[u])  
78.       {  
79.             int v = it.v;  
80.             int w = it.w;  
81.             if (v == p) continue;  
82.             dfs(v, u, x^w);  
83.       }  
84. }  
85.   
86. int main()  
87. {  
88.       //freopen("in.txt", "r", stdin);  
89.   
90.       int tc;  
91.       scanf("%d", &tc);  
92.       for (int tcase = 1; tcase <= tc; tcase++)  
93.       {  
94.             int tnode;  
95.             scanf("%d", &tnode);  
96.             for (int e = 1; e < tnode; e++)  
97.             {  
98.                   int u, v, w;  
99.                   scanf("%d %d %d", &u, &v, &w);  
100.                   graph[u].push_back(node(v, w));  
101.                   graph[v].push_back(node(u, w));  
102.             }  
103.             dfs();  
104.             fwt.self_convolution(arr, N);  
105.             ll zero = (arr[0] - tnode) >> 1;  
106.             printf("Case %d:\n", tcase);  
107.             printf("%lld\n", zero);  
108.             for (int i = 1; i < (1<<16); i++) printf("%lld\n", arr[i]>>1);  
109.             for (int i = 0; i < maxn; i++) graph[i].clear();  
110.             fill(begin(arr), end(arr), 0);  
111.       }  
112. }