点分治TLE on #9#10求助
查看原帖
点分治TLE on #9#10求助
760824
MornStar楼主2024/5/24 17:17
#include<bits/stdc++.h>
using namespace std;
const int N=20005;
int n,rt,ans,now_siz,siz[N],ma[N];
int dpre[3],dnow[3],dis[N];
bool vis[N];
struct edge{int to,w;};
vector<edge>e[N];
inline int Max(int a,int b){return (a>b?a:b);}
void get_rt(int now,int fa){
	siz[now]=1,ma[now]=0;
	for(auto it:e[now]){
		if(it.to!=fa&&!vis[it.to]){
			get_rt(it.to,now);
			siz[now]+=siz[it.to];
			ma[now]=Max(ma[now],siz[it.to]);
		}
	}
	ma[now]=Max(ma[now],now_siz-siz[now]);
	if(ma[now]<ma[rt])	rt=now;
}
void calc_dis(int now,int fa){
	dnow[dis[now]%3]++;
	for(auto it:e[now]){
		if(it.to!=fa&&!vis[it.to]){
			dis[it.to]=dis[now]+it.w;
			calc_dis(it.to,now);
		}
	}
}
void dfz(int now,int fa){
	vis[now]=1;
	dpre[0]=1,dpre[1]=dpre[2]=0;
	for(auto it:e[now]){
		if(it.to!=fa&&!vis[it.to]){
			dnow[0]=dnow[1]=dnow[2]=0;
			dis[it.to]=it.w;
			calc_dis(it.to,now);
			ans+=(dnow[0]*dpre[0]+dnow[1]*dpre[2]+dnow[2]*dpre[1])*2;
			for(int i=0;i<3;i++)	dpre[i]+=dnow[i];
		}
	}
	for(auto it:e[now]){
		if(it.to!=fa&&!vis[it.to]){
			now_siz=siz[it.to],rt=0;
			get_rt(it.to,now);get_rt(rt,now);
			dfz(it.to,now);
		}
	}
}
int gcd(int a,int b){return (b?gcd(b,a%b):a);}
int main(){
//	freopen("P2634_9.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin>>n;
	for(int i=1,u,v,w;i<n;i++){
		cin>>u>>v>>w;
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	ma[0]=0x3f3f3f3f;now_siz=n;
	get_rt(1,-1);get_rt(rt,-1);
	dfz(rt,-1);
	ans+=n;
	cout<<(ans/gcd(ans,n*n))<<"/"<<(n*n/gcd(ans,n*n))<<"\n";
}
2024/5/24 17:17
加载中...