求助,7RE+3MLE
查看原帖
求助,7RE+3MLE
752429
sutianyi楼主2023/8/10 09:34

代码越写越乱,我也不知道哪里错了,看了看题解,把自己看蒙了

#include<bits/stdc++.h>
const int maxn=200010;
using namespace std;
struct Node{
	long long v,w,next;
}e[maxn];
long long ans=-1,cnt,head[maxn],n,s,dp[2][maxn];
void dfs(int u,int fa){
	for(int i=head[u];i!=-1;i=e[i].next){
		if(e[i].v!=fa){
			int v=e[i].v,w=e[i].w;
			dfs(v,u);
			if(dp[0][v]+w>dp[0][u]){
				dp[1][u]=dp[0][u];
				dp[0][u]=dp[0][v]+w;
			}
			else if(dp[0][v]+w>dp[1][u]){
				dp[1][u]=dp[0][v]+w;
			}
		}
	}
	ans=max(ans,dp[0][u]+dp[1][u]);
	return;
}
inline void Init(){
	ans=-1;
	memset(head,-1,sizeof(head));
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++) 
			dp[i][j]=0;
	return;
}
inline void Add(int u,int v,int w){
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt++;
	return;
}
int main(){
	Init();
	cin >> n;
	for(int i=0;i<n-1;i++){
		int tu,tv,tk;	
		cin >> tu >> tv >> tk;
		Add(tu,tv,tk);
		Add(tv,tu,tk);
	}
	dfs(1,-1);
	long long tans=ans;
	cout << ans << endl;
	Init();
	for(long long i=0;i<cnt;i++){
		e[i].w-=1;
	}
	dfs(1,-1);
	cout << tans-ans;
	return 0;
}
2023/8/10 09:34
加载中...