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

题目大意

给定一棵带有边权的树, 问你在树上随机选两个点, 它们最短路径上的边权之和为\(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