题目大意

给定一棵带有边权的树, 问你在树上随机选两个点, 它们最短路径上的边权之和为\(4\)的倍数的概率为多少.

Solution

树分治. 没什么好讲的.

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;namespace Zeonfai{    inline int getInt()    {        int a = 0, sgn = 1; char c;        while(! isdigit(c = getchar())) if(c == '-') sgn *= -1;        while(isdigit(c)) a = a * 10 + c - '0', c = getchar();        return a * sgn;    }}const int N = (int)2e4;int n;int cnt[4];long long ans;struct tree{    struct edge    {        int v, w;        inline edge(int _v, int _w) {v = _v; w = _w;}    };    struct node    {        vector
         
           edg; int vst, sz, mx; inline node() {vst = 0; edg.clear();} }nd[N + 1]; inline void initialize() {for(int i = 1; i <= n; ++ i) nd[i] = node();} inline void addEdge(int u, int v, int w) {nd[u].edg.push_back(edge(v, w)); nd[v].edg.push_back(edge(u, w));} void getSize(int u, int pre) { nd[u].sz = 1; nd[u].mx = 0; for(auto edg : nd[u].edg) if(edg.v != pre && ! nd[edg.v].vst) getSize(edg.v, u), nd[u].sz += nd[edg.v].sz, nd[u].mx = max(nd[u].mx, nd[edg.v].sz); } int getRoot(int u, int pre, int cen) { nd[u].mx = max(nd[u].mx, nd[cen].sz - nd[u].sz); int res = u; for(auto edg : nd[u].edg) if(edg.v != pre && ! nd[edg.v].vst) { int cur = getRoot(edg.v, u, cen); if(nd[cur].mx < nd[res].mx) res = cur; } return res; } void getAnswer(int u, int pre, long long len) { ans += cnt[(4 - len % 4) % 4] << 1; for(auto edg : nd[u].edg) if(edg.v != pre && ! nd[edg.v].vst) getAnswer(edg.v, u, len + edg.w); } void update(int u, int pre, long long len) { ++ cnt[len % 4]; for(auto edg : nd[u].edg) if(edg.v != pre && ! nd[edg.v].vst) update(edg.v, u, len + edg.w); } inline void work(int u) { getSize(u, -1); u = getRoot(u, -1, u); memset(cnt, 0, sizeof(cnt)); cnt[0] = 1; ans += 1; for(auto edg : nd[u].edg) if(! nd[edg.v].vst) { getAnswer(edg.v, u, edg.w); update(edg.v, u, edg.w); } nd[u].vst = 1; for(auto edg : nd[u].edg) if(! nd[edg.v].vst) work(edg.v); } inline void work() {ans = 0; work(1);}}T;inline void output(long long a, long long b){ long long _a = a, _b = b; if(_a < _b) swap(_a, _b); while(_b) { long long tmp = _b; _b = _a % _b; _a = tmp; } printf("%lld/%lld\n", a / _a, b / _a);}int main(){#ifndef ONLINE_JUDGE freopen("AK.in", "r", stdin); freopen("AK.out", "w", stdout);#endif using namespace Zeonfai; while(n = getInt()) { T.initialize(); for(int i = 1, u, v, c; i < n; ++ i) u = getInt(), v = getInt(), c = getInt(), T.addEdge(u, v, c); T.work(); output(ans, (long long)n * n); }}