求助,WA最后一个点
查看原帖
求助,WA最后一个点
788023
ljiiua楼主2025/6/28 10:29
#include<iostream>
#include<cstdio>
using namespace std;
int n,head[202020],cnt;
struct node{
	int v,prep;
	long long w;
}edge[404040];
void add(int u,int v,long long w){
	edge[++cnt] = (node){v,head[u],w};
	head[u] = cnt;
}long long f[202020][2],g[202020][2],lsum[202020],rsum[202020],lst[202020],nxt[202020],son[202020];
void dfs1(int u,int fa){
	int pst = 0,st = 0;
	for(int i = head[u];i;i = edge[i].prep){
		int v = edge[i].v;
		if(v==fa) continue;
		dfs1(v,u);
		son[u]++;
		if(pst==0) st = v;
		nxt[pst] = v;
		lst[v] = pst;
		pst = v;
		lsum[v] = rsum[v] = max(f[v][0],(f[v][1]+edge[i].w)*(int)(son[v]>0));
		f[u][0] += lsum[v];
	}for(int i = st;i;i = nxt[i]) lsum[i] += lsum[lst[i]];
	for(int i = pst;i;i = lst[i]) rsum[i] += rsum[nxt[i]];
	for(int i = head[u];i;i = edge[i].prep){
		int v = edge[i].v;
		if(v==fa) continue;
		f[u][1] = max(f[u][1],lsum[lst[v]]+rsum[nxt[v]]+f[v][0]+edge[i].w);
	}
}void dfs2(int u,int fa){
	int maxv = 0,secv = 0;long long maxw = 0,secw = 0;
	for(int i = head[u];i;i = edge[i].prep){
		int v = edge[i].v;
		if(v==fa) continue;
		long long w = lsum[lst[v]]+rsum[nxt[v]]+f[v][0]+edge[i].w;
		if(w>=maxw) secv = maxv,maxv = v,secw = maxw,maxw = w;
		else if(w>secv) secv = v,secw = w;
	}for(int i = head[u];i;i = edge[i].prep){
		int v = edge[i].v;
		if(v==fa) continue;
		g[v][0] = lsum[lst[v]]+rsum[nxt[v]]+g[u][0];
		if(fa) g[v][0] = max(g[v][0],lsum[lst[v]]+rsum[nxt[v]]+g[u][1]+edge[i].w);
		if(son[u]>1){
			if(v!=maxv) g[v][0] = max(g[v][0],edge[i].w+maxw-max(f[v][0],(f[v][1]+edge[i].w)*(int)(son[v]>0))+g[u][0]);
			else g[v][0] = max(g[v][0],edge[i].w+secw-max(f[v][0],(f[v][1]+edge[i].w)*(int)(son[v]>0))+g[u][0]);
		}if(son[v]) g[v][1] = max(g[v][1],edge[i].w+lsum[lst[v]]+rsum[nxt[v]]+g[u][0]);
		dfs2(v,u);
	}
}
int main(){
	scanf("%d",&n);
	for(int i = 1;i<n;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);add(v,u,w);
	}dfs1(1,0);
	dfs2(1,0);
	long long res = 0;
	for(int i = 1;i<=n;i++){
		res = max(res,f[i][0]+g[i][0]);
		if(i!=1 && son[i]) res = max(res,f[i][1]+g[i][1]);
	}printf("%lld",res);
	return 0;
}
2025/6/28 10:29
加载中...