2152: Cong Cong Coco
Time Limit: 3 Sec Memory Limit: 259 MB
Submit: 3435 Solved: 1776
[Submit][Status][Discuss]
Description
Cong Cong and cocoa are two brothers, they often fight for some trivial things, such as home only the last Popsicle and two people want to eat, two people want to play computer (but they only have a computer)… Normally rock-paper-scissors would do, but they’re tired of playing low-iq games. Their dad was so bored with their arguments that he invented a new game in which dad drew n dots on a piece of paper and connected them with n-1 edges (it was a tree). And each edge has a number on it. Cong cong and Keke then choose a point (of course, they can’t see the tree when they choose the point). If the sum of all the edges between the two points is exactly a multiple of 3, Cong Cong wins, otherwise, Keke wins. Congcong was very thoughtful and would study the tree carefully after each game, hoping to know his winning probability for this picture. Please help to find out this value to verify whether Congcong’s answer is correct.
Input
The first line of the input contains a positive integer n. N minus 1 rows, each with three integers x, y, and w, indicate that there is a edge between x and y, and the number above is W.
Output
Output this probability as a reduced fraction (i.e., “A/B”, where a and B must be mutually qualitative. If the probability is 1, output “1/1”).
Sample Input
1 1 1 2 2 3 3\
Sample Output
13/25 point to the sample specification 】 【 13 group is (1, 1) (2, 2) (2, 3) and (2, 5) (3, 2) (3, 3) (3, 4) (3, 5) (4, 3) (4, 4) (5, 2) (5, 3) (5, 5). [Data size] For 100% data, n<=20000. \
HINT
Source
Title link: www.lydsy.com/JudgeOnline…
A naked tree divide and conquer
Let the distance between node I and the node currently divided and divided be dis[I]. For any point pair [I,j] that meets the condition, (dis[I] + dis[j]) % 3 = 0
We mod the dis[] value of all points to 3, and calculate the number of the result 0,1, and 2 after mod, denoted as num[0], NUM [1], num[2].
So, for any node I in the subtree:
1) dis[I] % 3 = 0: num[0] (multiple of 3);
2) dis[I] % 3 = 1: num[3-1 = 2]
If dis[I] is 3x + 1 and dis[j] is 3y + 2, then the sum is 3x + 1 + 3y + 2 = 3x + 3y + 3 = 3(x + y + 1), is a multiple of 3.
3) dis[I] % 3 = 2: num[3-2 = 1] (Proof as above)
The above situations can be combined into CNT += (! dis[i] ? Num [0] : num[3 – dis[I]])
Here is the AC code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 inline int read() 4 {5 int x=0,f=1; Char ch=getchar(); 7 while (ch < '0' | | ch > '9') / / if ch is not the number 8 {9 if (ch = = '-') / / if it is a symbol to change symbol 10 f = 1; 11 ch=getchar(); 12} 13 while (ch > = '0' && ch < = '9') / / if the ch is digital, the next each number 14 {15 x = x * 10 + ch - '0'; Ch =getchar(); 17 } 18 return x*f; 19} 20 Inline void write(int x) 21 {22 if(x<0) 23 {24 putchar('-'); 25 x=-x; 26} 27 if(x>9)// save each bit 28 {29 write(x/10); 30 } 31 putchar(x%10+'0'); 32} 33 Inline int GCD (int a,int b) 34 {35 return b==0? a:gcd(b,a%b); 36 } 37 const int N=20010; 38 int last[N]; 39 int son[N]; Int f[N]; Int d[N]; int d[N]; Int t[N]; Bool vis[N]; Struct Edge 45 {46 int to,next,v; 47 }edge[N<<1]; Int n, CNT,ans,root,sum; 49 Inline void addage(int u,int v,int w) {50 edge[++ CNT]. To =v; 52 edge[cnt].next=last[u]; 53 last[u]=cnt; 54 edge[cnt].v=w; 55 edge[++cnt].to=u; 56 edge[cnt].next=last[v]; 57 last[v]=cnt; 58 edge[cnt].v=w; 59} 60 inline void getroot(int x,int fa) 61 {62 son[x]=1; F [x]=0; //son[x] =0; For (int I =last[x]; i; I =edge[I].next)// enumerate every point adjacent to x 65 {66 if(! vis[edge[i].to]&&edge[i].to! 67 {68 getroot(edge[I].to,x); 69 son[x]+=son[edge[i].to]; F [x]= Max (f[x],son[I].to]); 71 } 72 } 73 f[x]=max(f[x],sum-son[x]); / / the number of nodes in the tree of architectural f x [x] = Max (f (x), with the subtree size - f [x]) 74 if (f [x] < f 75 root = x (root)); 76} 77 Inline void getdeep(int x,int fa)// Get the distance between each point and x in CAL, root 78 {79 t[d[x]]++; For (int I =last[x]; int I =last[x]; i; I =edge[I].next)// enumerate every point adjacent to x 81 {82 if(! vis[edge[i].to]&&edge[i].to! = fa) / / if you don't have to be deleted, and the current node is not the root node 83 {84 [edge [I] to] = d (d + edge [I] [x] v) % 3. 85 getdeep(edge[i].to,x); 86 } 87 } 88 } 89 inline int cal(int x,int Now) / / t [0] said to k % 3 = 0, the number of points, t [1] said the remainder is 1, t [2] said the remainder is 2, so the calculation of solution, t [0] internally, t [1] and [2] t match two 90 {[0] = 91 t t [1] [2] = t = 0. D [x]=now; 93 getdeep(x,0); Root 94 return t[1]*t[2]*2+t[0]*t[0]; 95} 96 Inline void work(int x) {98 ans+= CAL (x,0); Vis [x]=1; vis[x]=1; For (int I =last[x]; i; I =edge[I].next)// enumerate every point adjacent to x 101 {102 if(! Vis [edge[I].to]) {104 ans-= CAL (edge[I].to,edge[I].v); // Remove 105 root=0; 106 sum=son[edge[i].to]; 107 getroot(edge[i].to,0); Root 108 work(root); 109} 110} 111} 112 int main() 113 {114 n=read(); 115 for(int i=1; i<n; Int u=read(); 118 int v=read(); 119 int w=read()%3; 120 addage(u,v,w); F [0]=n; 123 sum=n; 124 getroot (1, 0); 125 work(root); 126 int t=gcd(ans,n*n); 127 printf("%d/%d\n",ans/t,n*n/t); 128 return 0; 129}Copy the code