[Luogu P2634] [国家集训队]聪聪可可

[Luogu P2634] [国家集训队]聪聪可可

思路

点分治入门题,用数组记录长度为$0, 1, 2\pmod 3$的路径条数,运用容斥原理统计一下即可

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

struct Edge;
struct Node{
    Edge *head;
    int siz, mx, dep;
    bool vis;
}node[20010], *root;
struct Edge{
    Node *to;
    Edge *ne;
    int val;
    Edge(int x, int y, int z):to(&node[y]), ne(node[x].head), val(z){}
};
int n, SumSiz, cnt[3], ans;

void getroot(Node *x, Node *fa){
    x->siz=1, x->mx=0;
    for(Edge *i=x->head; i; i=i->ne){
        if(i->to->vis || i->to==fa)	continue;
        getroot(i->to, x);
        x->siz+=i->to->siz;
        x->mx=max(x->mx, i->to->siz);
    }
    x->mx=max(x->mx, SumSiz-x->siz);
    root=root ? (x->mx<root->mx ? x : root) : x;
}

void dfs1(Node *x, Node *fa){
    cnt[x->dep]++;
    for(Edge *i=x->head; i; i=i->ne){
        if(i->to==fa || i->to->vis)	continue;
        i->to->dep=(x->dep+i->val)%3;
        dfs1(i->to, x);
    }
}

int solve(Node *x, int y){
    memset(cnt, 0, sizeof(cnt));
    x->dep=y%3;
    dfs1(x, NULL);
    return cnt[1]*cnt[2]*2+cnt[0]*cnt[0];
}

void divide(Node *x){
    ans+=solve(x, 0);
    x->vis=true;
    for(Edge *i=x->head; i; i=i->ne){
        if(i->to->vis)	continue;
        ans-=solve(i->to, i->val);
        SumSiz=i->to->siz, root=NULL;
        getroot(i->to, NULL);
        divide(root);
    }
}

int gcd(int x, int y){return x ? gcd(y%x, x) : y;}

int main(){
    int x, y, z;
    scanf("%d", &n);
    SumSiz=n;
    for(int i=1; i<n; i++){
        scanf("%d%d%d", &x, &y, &z);
        node[x].head=new Edge(x, y, z);
        node[y].head=new Edge(y, x, z);
    }
    root=NULL;
    getroot(&node[1], NULL);
    divide(root);
    int qwq=gcd(ans, n*n);
    printf("%d/%d", ans/qwq, n*n/qwq);
    return 0;
}

[Luogu P2634] [国家集训队]聪聪可可》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注