NOIP2016模拟赛三 Problem C: 不虚就是要AK

题目大意

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

Solution

树分治. 没什么好讲的.

#include <cstdio>

#include <cctype>

#include <vector>

#include <algorithm>

#include <cstring>

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<edge> 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);

    }

}