萌新的巨大常数点分治,求调
查看原帖
萌新的巨大常数点分治,求调
469066
zzxLLL楼主2022/2/4 00:23

#9 #10 TLE

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=2e4+10;

inline int read(){
	int x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	return x;
}

int n;
struct node{
	int to,next,dis;
}edge[M<<1];
int head[M],cnte;
inline void add(int u,int v,int w){
	edge[++cnte].to=v;
	edge[cnte].dis=w;
	edge[cnte].next=head[u];
	head[u]=cnte;
}

bool vis[M];
int f[M],size[M],S,root;
inline void getroot(int u,int fa){
	f[u]=0,size[u]=1;
	for(int i=head[u];~i;i=edge[i].next){
		int v=edge[i].to;
		if(!vis[v]&&v!=fa){
			getroot(v,u);
			size[u]+=size[v];
			f[u]=max(f[u],size[v]);
		}
	}
	f[u]=max(f[u],S-size[u]);
	if(f[u]<f[root]) root=u;
}

int d[M],buc[3];
inline void getdep(int u,int fa){
	buc[d[u]%3]++;
	for(int i=head[u];~i;i=edge[i].next){
		int v=edge[i].to;
		if(!vis[v]&&v!=fa){
			d[v]=d[u]+edge[i].dis;
			getdep(v,u);
		}
	}
}

inline int getans(int u,int dis){
	buc[0]=buc[1]=buc[2]=0;
	d[u]=dis,getdep(u,0);
	return buc[0]*buc[0]+buc[1]*buc[2]*2;
}

int ans;
inline void solve(int u){
	vis[u]=true,getdep(u,0);
	ans+=getans(u,0);
	for(int i=head[u];~i;i=edge[i].next){
		int v=edge[i].to;
		if(!vis[v]){
			ans-=getans(v,edge[i].dis);
			S=size[v],root=0;
			getroot(v,0),solve(v);
		}
	}
}

inline int gcd(int A,int B){
	return B==0?A:gcd(B,A%B);
}

int main(){
	memset(head,-1,sizeof head);
	n=read();
	for(int i=1,u,v,w;i<n;i++){
		u=read(),v=read(),w=read();
		add(u,v,w),add(v,u,w);
	}
	f[0]=S=n;
	getroot(1,0),solve(root);
	
	int GCD=gcd(ans,n*n);
	printf("%d/%d",ans/GCD,n*n/GCD);
	return 0;
}
2022/2/4 00:23
加载中...