公司网站制作投标,彬县网约车,用php做的订票网站,app推广软件链接#xff1a;https://www.luogu.org/problemnew/show/P2634 题目描述 聪聪和可可是兄弟俩#xff0c;他们俩经常为了一些琐事打起来#xff0c;例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑#xff08;可是他们家只有一台电脑#xff09;……遇到这种问…链接https://www.luogu.org/problemnew/show/P2634 题目描述 聪聪和可可是兄弟俩他们俩经常为了一些琐事打起来例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑可是他们家只有一台电脑……遇到这种问题一般情况下石头剪刀布就好了可是他们已经玩儿腻了这种低智商的游戏。 他们的爸爸快被他们的争吵烦死了所以他发明了一个新游戏由爸爸在纸上画n个“点”并用n-1条“边”把这n个“点”恰好连通其实这就是一棵树。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点当然他们选点时是看不到这棵树的如果两个点之间所有边上数的和加起来恰好是3的倍数则判聪聪赢否则可可赢。 聪聪非常爱思考问题在每次游戏后都会仔细研究这棵树希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。 输入输出格式 输入格式 输入的第1行包含1个正整数n。后面n-1行每行3个整数x、y、w表示x号点和y号点之间有一条边上面的数是w。 输出格式 以即约分数形式输出这个概率即“a/b”的形式其中a和b必须互质。如果概率为1输出“1/1”。 输入输出样例 输入样例#1 复制 5
1 2 1
1 3 2
1 4 1
2 5 3 输出样例#1 复制 13/25 说明 【样例说明】 13组点对分别是(1,1) (2,2) (2,3) (2,5) (3,2) (3,3) (3,4) (3,5) (4,3) (4,4) (5,2) (5,3) (5,5)。 【数据规模】 对于100%的数据n20000。 题解点分治 统计出 dis%3 的条数对该点的贡献就是 tong[0] * tong[0] tong[1] * tong[2] 这次点分又写错了我求了重心结果dfs的时候还是在用儿子节点 #includebits/stdc.h
using namespace std;
const int M 50005;
int h[M], siz[M], sum, Ans, tot, cnt, tong[3], dep[M], son[M], tmp[M], root;
bool vis[M];
struct edge{int v, w, nxt;}G[M 1];
void add(int u, int v, int w){G[tot].v v; G[tot].w w; G[tot].nxt h[u]; h[u] tot;}
int gcd(int a, int b){return b ? gcd(b, a%b) : a;}
inline int moc(int a){return a 3 ? a - 3 : a;}
void getdeep(int u, int fa){for(int i h[u]; i; i G[i].nxt){int v G[i].v;if(v fa || vis[v])continue;tong[ dep[v] moc(dep[u] G[i].w)];getdeep(v, u);}
}int cal(int u, int k){int ret 0;tong[0] tong[1] tong[2] 0;tong[dep[u] k] ;getdeep(u, u);ret tong[0]*tong[0] tong[1] * tong[2] * 2;return ret;
}
void getroot(int u, int fa){siz[u] 1; son[u] 0;for(int i h[u]; i; i G[i].nxt){int v G[i].v;if(v fa || vis[v])continue;getroot(v, u);siz[u] siz[v];if(siz[v] siz[son[u]])son[u] v;}tmp[u] max(siz[son[u]], sum - siz[u]);if(tmp[u] tmp[root]) root u;
}void dfs(int u, int fa){Ans cal(u, 0);//printf( %d %d\n, Ans, u);vis[u] 1;for(int i h[u]; i; i G[i].nxt){int v G[i].v;if(v fa|| vis[v])continue;Ans - cal(v, G[i].w);sum siz[v]; getroot(v, root 0);// printf(- %d %d\n, Ans, v);dfs(root, 0);}}
int read(){int x0,f1;char cgetchar();while(c0||c9){if(c-)f-1;cgetchar();}while(c9c0){xx*10c-0;cgetchar();}return x*f;
}
int main(){//freopen(1.in,r,stdin);int n;scanf(%d, n);int u, v, w;for(int i 1; i n; i){u read(), v read(), w read();w % 3;add(u, v, w), add(v, u, w);}tmp[0] 1e9;int cc clock();dfs(1, 0);//Ans Ans n;int tt n * n;int d gcd(tt, Ans);printf(%d/%d\n, Ans/d, tt/d);int tm clock();//couttm-ccendl;
}/*
10000000
6
1 2 1
1 3 2
1 4 1
2 5 3
3 6 3
*/ View Code 转载于:https://www.cnblogs.com/EdSheeran/p/9470026.html
