专栏首页小樱的经验随笔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 1

Output

1265625

Input

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 0

Output

452841614

Note

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces 626E Simple Skewness(暴力枚举+二分)

    E. Simple Skewness time limit per test:3 seconds memory limit per test:256 megab...

    Angel_Kitty
  • AIM Tech Round 4 (Div. 2)(A,暴力,B,组合数,C,STL+排序)

    A. Diversity time limit per test:1 second memory limit per test:256 megabytes in...

    Angel_Kitty
  • POJ 1012 Joseph

    Joseph Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 53862 ...

    Angel_Kitty
  • Codeforces 626E Simple Skewness(暴力枚举+二分)

    E. Simple Skewness time limit per test:3 seconds memory limit per test:256 megab...

    Angel_Kitty
  • HDU 3032 Nim or not Nim?(Multi-Nim)

    Problem Description Nim is a two-player mathematic game of strategy in which ...

    attack
  • 【Codeforces】1213B - Bad Prices

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • POJ 3037 Skiing(Dijkstra)

    Skiing Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4668 ...

    ShenduCC
  • POJ--1699 Best Sequence(DP+dfs)

    Best Sequence Time Limit: 1000MS Memory Limit: 10000K Total Submissions...

    ShenduCC
  • POJ 2594 Treasure Exploration

    Description Have you ever read any book about treasure exploration? Have you ev...

    attack
  • P2880 [USACO07JAN]平衡的阵容Balanced Lineup

    题目背景 题目描述: 每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛....

    attack

扫码关注云+社区

领取腾讯云代金券