30分求调
查看原帖
30分求调
917683
rnf5114楼主2024/10/21 13:16
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,dp[200010][3],tmp[200010],s,ans;
struct node{
	int y,z;
};
vector<node>v[200010];
void Dfs(int x,int Fa){
	for(int i=0;i<v[x].size();i++){
		int y=v[x][i].y;
		if(y==Fa)
			continue;
		Dfs(y,x);
		if(dp[x][0]<dp[y][0]+v[x][i].z)
			dp[x][1]=dp[x][0],dp[x][0]=dp[y][0]+v[x][i].z;
		else if(dp[x][1]<dp[y][0]+v[x][i].z)
			dp[x][1]=dp[y][0]+v[x][i].z;
		ans=max(ans,dp[x][0]+dp[x][1]);
	}
}
void dfs(int x,int Fa){
//	cout<<"qwq"<<ans<<" "<<x<<" "<<Fa<<"\n";
	set<int>st;
	map<int,int>m;
	for(int i=1;i<=v[x].size();i++){
		int y=v[x][i-1].y;
		if(y==Fa)
			continue;
		st.insert(dp[y][0]+v[x][i-1].z);
//		cout<<"!!!"<<y<<" "<<dp[y][0]+v[x][i-1].z<<"\n";
		m[dp[y][0]+v[x][i-1].z]++;
	}
	if(st.end()==st.begin())
		return ;
//	cout<<x<<" "<<m[*(--st.end())]<<"\n";
	if(m[*(--st.end())]>2)
		return ;
	else if(m[*(--st.end())]==2&&x==1){
		for(int i=1;i<=v[x].size();i++){
			int y=v[x][i-1].y;
			if(y==Fa)
				continue;
			if(dp[y][0]+v[x][i-1].z==*(--st.end()))
				ans++,dfs(y,x);
		}
	}
	else if(m[*(--st.end())]==1){
		for(int i=1;i<=v[x].size();i++){
			int y=v[x][i-1].y;
			if(y==Fa)
				continue;
//			cout<<ans<<" "<<(*(--(--st.end())))<<"\n";
			if(st.size()>=2&&m[*(--(--st.end()))]==1&&x==1&&(*(--(--st.end())))==dp[y][0]+v[x][i-1].z)
				ans++,dfs(y,x);
			if(dp[y][0]+v[x][i-1].z==*(--st.end()))
				ans++,dfs(y,x);
		}
	}
	else
		return ;
}
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		v[x].push_back({y,z}),v[y].push_back({x,z});
	}
	Dfs(1,0);
	cout<<ans<<"\n";
	ans=0;
	dfs(1,0);
	cout<<ans<<"\n";
	return 0;
}

/*

もうやり残すこともない

あぁ でも 少し待って

一つくらい後悔がある

貴方と過ごした最後の日

「貴方は私の全てだ」

そんな思いを話し出す前に

私は唇を噛み 言葉を飲み込んだ我

ただ麦芽飴(マイヤータン)を舐め続けた

       ┏┓   ┏┓
     ┏┛┻━━━┛┻┓
     ┃       ┃
     ┃   ━   ┃
     ┃ ┳┛ ┗┳ ┃      orz神兽保佑代码无bug
     ┃       ┃
     ┃   ┻   ┃
     ┃       ┃
     ┗━┓   ┏━┛
         ┃   ┃
         ┃   ┃
         ┃   ┗━━━┓
         ┃      ┣┓
         ┃     ┏┛
         ┗┓┓┏━┳┓┏┛
           ┃┫┫ ┃┫┫
           ┗┻┛ ┗┻┛

*/

2024/10/21 13:16
加载中...