只有#1AC,玄学错误,马蜂良好有注释,求条
查看原帖
只有#1AC,玄学错误,马蜂良好有注释,求条
764773
AstaVenti_楼主2025/1/24 10:02
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=200005;
vector<pair<ll,ll>>e[maxn];
ll mx[maxn],sz[maxn],vis[maxn],d[maxn],q[maxn],dis[maxn],ans[maxn],zbq=0,ednd,zj;
ll n,m,tot,rt,cnt,hav[10000007];
void qzj(ll u,ll fa,ll dis) {
    if (dis>zj) zj=dis,ednd=u;
    for(auto a:e[u]) {
    	ll v=a.first;
        if(v!=fa)qzj(v,u,dis+a.second);
    }
}//求直径 
void fdrt(ll u,ll fa){
	sz[u]=1,mx[u]=0;
	for(auto a:e[u]){
		ll v=a.first;
		if(v!=fa&&!vis[v]){
			fdrt(v,u),sz[u]+=sz[v],mx[u]=max(mx[u],sz[v]);
		}
	}
	mx[u]=max(mx[u],tot-sz[u]);
	if(mx[u]<mx[rt])rt=u;
}
void gtds(ll u,ll fa){
	d[++cnt]=dis[u];
	for(auto a:e[u]){
		ll v=a.first;
		if(v!=fa&&!vis[v]){
			dis[v]=dis[u]+a.second,gtds(v,u);
		}
	}
}

void pd(ll u){
	hav[0]=1;
	vector<ll>ve;
	for(auto a:e[u]){
		ll v=a.first;
		if(!vis[v]){
			cnt=0;
			dis[v]=a.second;
			gtds(v,u);
			for(ll j=1;j<=cnt;j++){
				for(ll k=1;k<=m;k++){
					if(q[k]>=d[j])
						ans[k]+=hav[q[k]-d[j]];
				}
			}
			for(ll j=1;j<=cnt;j++){
				if(d[j]<1e7){
					hav[d[j]]=1;
					ve.push_back(d[j]);
				}
			}
		}
	}
	for (auto v:ve)
		hav[v]=0;
}
void dfz(ll u){
	pd(u),vis[u]=1;
	for(auto a:e[u]){
		ll v=a.first;
		if(!vis[v]){
			rt=0,mx[0]=tot=sz[v],fdrt(v,0),fdrt(rt,0),dfz(rt);
		}
	}
}//以上是板子 
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	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});
	}
	qzj(1,-1,0),qzj(ednd,-1,0);
	m=zj;
	for(int i=1;i<=zj;i++){
		q[i]=i;
	}//zj次询问,每次一个长度 
	mx[0]=tot=n;
	ll ANS=n,SUM=n*n;//ANS是可行方案,SUM是总方案 
	fdrt(1,0),fdrt(rt,0),dfz(rt);
	for(int i=0;i<=zj;i+=3){
//		cout<<i<<" "<<ans[i]<<endl;
		ANS+=ans[i]*2;//考虑顺序 
//		cout<<ANS<<endl;
	}
//	cout<<ANS<<"/"<<SUM<<endl;
	ll GCD=__gcd(ANS,SUM);
	ANS/=GCD,SUM/=GCD;
	cout<<ANS<<"/"<<SUM;
}//郭进禄 刘晓觅 

2025/1/24 10:02
加载中...