0pts玄关求调 Orz
查看原帖
0pts玄关求调 Orz
984202
Qinkaixi666楼主2024/11/8 22:04
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<set>
#include<ctime>
#define ls t*2
#define rs t*2+1
using namespace std;
const int N=20005;
int nxt[N*2],to[N*2],dis[N*2],head[N],tot,n;
int maxn[N],sum,rt,sz[N],vis[N];
int rem[4],judge[4],ans,ans2;  //rem[i]当前子数路径 %3==i 的路径数
inline int read(){
    int f=1,ss=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ss=ss*10+c-'0';c=getchar();}
    return ss*f;
}
void add(int x,int y,int z){
    nxt[++tot]=head[x];head[x]=tot;
    to[tot]=y;dis[tot]=z;
}
void getrt(int u,int fa){
    maxn[u]=0;sz[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(v==fa||vis[v]) continue;
        getrt(v,u);
        sz[u]+=sz[v];
        maxn[u]=max(maxn[u],sz[v]);
    }
    maxn[u]=max(maxn[u],sum-maxn[u]);
    if(maxn[rt]>maxn[u]) rt=u;
}
void getdis(int u,int fa,int  nw){
    rem[nw]++;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(v==fa||vis[v]) continue;
        getdis(v,u,(nw+dis[i])%3);
    }
}
void calc(int u){
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(vis[v]) continue;
        getdis(v,u,dis[i]%3);
        ans=ans+2*judge[2]*rem[1]+rem[0]*2+2*judge[1]*rem[2];
        for(int j=0;j<=2;j++) judge[j]+=rem[j],rem[j]=0;
    }
    for(int j=0;j<=2;j++) judge[j]=0;
}
void solve(int u,int fa){
    vis[u]=1;calc(u);
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(v==fa||vis[v]) continue;
        maxn[rt=0]=N;sum=sz[v];
        getrt(v,u);solve(rt,u);
    }
}
signed main(){
    freopen("cchmm.in","r",stdin);
    freopen("cchmm.out","w",stdout);
    n=read();ans2=n*n;ans=n;
    for(int x,y,z,i=1;i<n;i++){
        x=read();y=read();z=read()%3;
        add(x,y,z);add(y,x,z);
    }
    maxn[rt=0]=sum=n;
    getrt(1,0);
    solve(rt,0);
    for(int i=n;i>=2;i--) if(ans%i==0 && ans2%i==0) ans/=i,ans2/=i;
    printf("%d/%d",ans,ans2);
    return 0;
}


2024/11/8 22:04
加载中...