Codeforces 833D Red-black Cobweb【树分治】
Codeforces 833D Red-black Cobweb【树分治】
D. Red-black Cobweb
time limit per test：6 seconds
memory limit per test：256 megabytes
input：standard input
output：standard output
Slastyona likes to watch life of nearby grove's dwellers. This time she watches a strange red-black spider sitting at the center of a huge cobweb.
The cobweb is a set of n nodes connected by threads, each of the treads is either red of black. Using these threads, the spider can move between nodes. No thread connects a node to itself, and between any two nodes there is a unique sequence of threads connecting them.
Slastyona decided to study some special qualities of the cobweb. She noticed that each of the threads has a value of clamminess x.
However, Slastyona is mostly interested in jelliness of the cobweb. Consider those of the shortest paths between each pair of nodes on which the numbers of red and black threads differ at most twice. For each such path compute the product of the clamminess of threads on the path.The jelliness of the cobweb is the product of all obtained values among all paths. Those paths that differ by direction only are counted only once.
Of course, this number can be huge, so Slastyona asks you to compute the jelliness of the given cobweb and print the answer modulo 109 + 7.
Input
The first line contains the number of nodes n (2 ≤ n ≤ 105).
The next n - 1 lines contain four integers each, denoting the i-th thread of the cobweb: the nodes it connects ui, vi (1 ≤ ui ≤ n, 1 ≤ vi ≤ n), the clamminess of the thread xi (1 ≤ x ≤ 109 + 6), and the color of the thread ci (
). The red color is denoted by 0, and the black color is denoted by 1.
Output
Print single integer the jelliness of the cobweb modulo 109 + 7. If there are no paths such that the numbers of red and black threads differ at most twice, print 1.
Examples
Input
5
1 2 9 0
2 3 5 1
2 4 5 0
2 5 5 1Output
1265625Input
8
1 2 7 1
2 3 4 1
3 4 19 1
5 1 2 0
6 2 3 0
7 3 3 0
8 4 4 0Output
452841614Note
In the first example there are 4 pairs of nodes such that the numbers of threads of both colors on them differ at most twice. There pairs are (1, 3) with product of clamminess equal to 45, (1, 5) with product of clamminess equal to 45, (3, 4) with product of clamminess equal to 25 and (4, 5) with product of clamminess equal to 25. The jelliness of the cobweb is equal to 1265625.
题目链接：http://codeforces.com/contest/833/problem/D
官方题解：
下面给出AC代码：
1 #include <cstdio>
2 #include <cstring>
3 #include <utility>
4 #include <vector>
5
6 const int N = 100000;
7 const int MOD = (int)1e9 + 7;
8
9 struct Edge { int v, x, c; };
10 struct Sum { int c, p; };
11
12 Sum& operator += (Sum& a, const Sum& b)
13 {
14 a.c += b.c;
15 a.p = (long long)a.p * b.p % MOD;
16 }
17
18 int n, m, result, size[N], imbalance[N], w[2];
19 bool resolved[N];
20 Sum sum[N << 2];
21 std::vector<int> vertices;
22 std::vector<std::pair<int, int>> todos;
23 std::vector<Edge> tree[N];
24
25 int pow(int a, int n)
26 {
27 int result = 1;
28 while (n) {
29 if (n & 1) {
30 result = (long long)result * a % MOD;
31 }
32 a = (long long)a * a % MOD;
33 n >>= 1;
34 }
35 return result;
36 }
37
38 int prepare(int p, int u)
39 {
40 int size = 1;
41 for (auto&& iterator : tree[u]) {
42 auto v = iterator.v;
43 if (v != p) {
44 int s = prepare(u, v);
45 result = (long long)result * pow(iterator.x, (long long)s * (n - s) % (MOD - 1)) % MOD;
46 size += s;
47 }
48 }
49 return size;
50 }
51
52 int prepare2(int p, int u)
53 {
54 vertices.push_back(u);
55 size[u] = 1, imbalance[u] = 0;
56 for (auto&& iterator : tree[u]) {
57 auto&& v = iterator.v;
58 if (v != p && !resolved[v]) {
59 prepare2(u, v);
60 size[u] += size[v];
61 imbalance[u] = std::max(imbalance[u], size[v]);
62 }
63 }
64 }
65
66 void add(int k, const Sum& v)
67 {
68 for (; k < m << 2; k += ~k & k + 1) {
69 sum[k] += v;
70 }
71 }
72
73 void dfs(int p, int u, int offset, int product)
74 {
75 todos.emplace_back(offset, product);
76 Sum s {0, 1};
77 for (int k = offset - 1; k >= 0; k -= ~k & k + 1) {
78 s += sum[k];
79 }
80 result = (long long)result * pow((long long)pow(product, s.c) * s.p % MOD, MOD - 2) % MOD;
81 for (auto&& iterator : tree[u]) {
82 auto&& v = iterator.v;
83 if (v != p && !resolved[v]) {
84 dfs(u, v, offset + w[iterator.c], (long long)product * iterator.x % MOD);
85 }
86 }
87 }
88
89 void divide(int root)
90 {
91 vertices.clear();
92 prepare2(-1, root);
93 m = size[root];
94 for (auto&& u : vertices) {
95 imbalance[u] = std::max(imbalance[u], m - size[u]);
96 }
97 for (auto&& u : vertices) {
98 if (imbalance[u] < imbalance[root]) {
99 root = u;
100 }
101 }
102 for (int t = 0; t < 2; ++ t) {
103 w[t] = 1, w[t ^ 1] = -2;
104 for (int i = 0; i < m << 2; ++ i) {
105 sum[i] = {0, 1};
106 }
107 add(m << 1, {1, 1});
108 for (auto&& iterator : tree[root]) {
109 auto&& v = iterator.v;
110 if (!resolved[v]) {
111 dfs(root, v, (m << 1) + w[iterator.c], iterator.x);
112 for (auto&& todo : todos) {
113 add((m << 2) - todo.first, {1, todo.second});
114 }
115 todos.clear();
116 }
117 }
118 }
119 resolved[root] = true;
120 for (auto&& iterator : tree[root]) {
121 auto&& v = iterator.v;
122 if (!resolved[v]) {
123 divide(v);
124 }
125 }
126 }
127
128 int main()
129 {
130 #ifdef LOCAL_JUDGE
131 freopen("D.in", "r", stdin);
132 #endif
133 while (scanf("%d", &n) == 1) {
134 for (int i = 0; i < n; ++ i) {
135 tree[i].clear();
136 }
137 for (int i = 0, a, b, x, c; i < n - 1; ++ i) {
138 scanf("%d%d%d%d", &a, &b, &x, &c);
139 a --;
140 b --;
141 tree[a].push_back({b, x, c});
142 tree[b].push_back({a, x, c});
143 }
144 result = 1;
145 prepare(-1, 0);
146 memset(resolved, 0, sizeof(*resolved) * n);
147 divide(0);
148 printf("%d\n", result);
149 }
150 }