Mn Zn 刚学点分治,模板求调,0分
查看原帖
Mn Zn 刚学点分治,模板求调,0分
757101
junee楼主2024/3/9 15:40
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e4+10;
int h[N],e[N*2],ne[N*2],w[N*2],idx;
int st[N];
int p[N],q[N];
int b[4];
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
void add(int a,int b,int c){
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int get_sz(int u,int f){
    if(st[u])return 0;
    int sz=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==f)continue;
        sz+=get_sz(j,u);
    }
    return sz;
}
void get_dist(int u,int f,int dist,int &qt){
    if(st[u])return;
    q[qt++]=dist;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==f)continue;
        get_dist(j,u,dist+w[i],qt);
    }
}
int get_ws(int u,int f,int tot,int &ws){
    if(st[u])return 0;
    int sum=1,ms=0;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==f)continue;
        int t=get_ws(j,u,tot,ws);
        ms=max(ms,t);
        sum+=t;
    }
    ms=max(ms,tot-sum);
    if(ms<=tot/2)ws=u;
    return sum;
}
int get(int a[],int k){
	b[0]=b[1]=b[2]=0;
	for(int i=0;i<k;i++)b[a[i]%3]++;
	return b[0]*b[0]+b[1]*b[2]*2;
}
int calc(int u){
	if(st[u])return 0;
	get_ws(u,-1,get_sz(u,-1),u);
	st[u]=1;
	int ans=1;
	int pt=0;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i],qt=0;
		get_dist(j,u,w[i]%3,qt);
		ans-=get(q,qt);
		for(int k=0;k<qt;k++){
			if(q[k]==0)ans++;
			p[pt++]=q[k];
		}
	}
	ans+=get(p,pt);
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		ans+=calc(j);
	} 
	return ans;
}
int main(){
	memset(h,-1,sizeof h);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	int tot=n*n;
	int ans=calc(1);
	if(ans==tot)cout<<"1/1";
	else cout<<ans/gcd(tot,ans)<<"/"<<tot/gcd(tot,ans);
	return 0;
}
2024/3/9 15:40
加载中...