1 条题解

  • 0
    @ 2025-12-27 21:38:07
    
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 2e4 + 4;
    vector< pair<int, int> > G[N];
    int n, ans;
    int siz[N], all, rt, rtmaxsiz;
    int dis[N], t[4];
    bool del[N];
    
    void getroot(int x, int xfa)
    {
        siz[x] = 1;
        int xmaxsiz = 0;
        for (auto i:G[x])
            if (i.first != xfa && !del[i.first]){
                getroot(i.first, x);
                siz[x] += siz[i.first];
                xmaxsiz = max(xmaxsiz, siz[i.first]);
            }
        xmaxsiz = max(xmaxsiz, all - siz[x]);
        if (xmaxsiz < rtmaxsiz) rtmaxsiz = xmaxsiz, rt = x;
    }
    
    void getdis(int x, int xfa)
    {
        t[dis[x]]++;
        for (auto i:G[x])
            if (i.first != xfa && !del[i.first]){
                dis[i.first] = (dis[x] + i.second)%3;
                getdis(i.first, x);
            }
    }
    
    int calc(int x,int w)
    {
        t[0]=t[1]=t[2]=0;
        dis[x]=w;
        getdis(x, 0);
        return t[1]*t[2]*2 + t[0]*t[0];
    }
    
    void divide(int x)
    {
        ans+=calc(x,0);
        del[x] = true;
        for (auto i:G[x])
            if (!del[i.first]){
                ans-=calc(i.first,i.second);
                all=rtmaxsiz=siz[i.first];getroot(i.first, x);getroot(rt, x);
                divide(rt);
            }
    }
    int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}
    int main()
    {
        ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
        cin >> n ;
        for (int i = 2, x, y, w; i <= n; i++)
        {
            cin >> x >> y >> w; w%=3;
            G[x].push_back({y, w});
            G[y].push_back({x, w});
        }
    
        ans = 0;
    
        all=rtmaxsiz=n;getroot(1, 0);getroot(rt, 0);
        divide(rt);
    
        int g= gcd(ans,n*n);
    
        cout << ans/g << "/" << n*n/g << "\n"  ;
        return 0;
    }
    
    
    • 1

    C13_2【点分治】[国家集训队] 聪聪可可

    信息

    ID
    3817
    时间
    1000ms
    内存
    128MiB
    难度
    7
    标签
    递交数
    22
    已通过
    8
    上传者