C++14(g++5.4) 解法, 执行用时: 344ms, 内存消耗: 29772K, 提交时间: 2020-06-01 16:17:57

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int e[N<<2],ne[N<<2],w[N<<2],h[N<<2],idx;
int t,n,ans;
int f[N];
void add(int a,int b,int c)
{
	e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int u,int fa)
{
	for(int i=h[u];~i;i=ne[i])
	{
		int v=e[i];
		if(v==fa) continue;
		dfs(v,u);
		ans=max(ans,f[u]+f[v]+w[i]);
	//	cout<<ans<<endl;
		f[u]=max(f[u],f[v]+w[i]);
	}
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		idx=0;
		memset(h,-1,sizeof h);
		ans=-0x3f3f3f3f;
		for(int i=2,u,c;i<=n;i++)
		{
			scanf("%d %d",&u,&c);
			add(u,i,c);
			add(i,u,c);
		}
		for(int i=1;i<=n;i++) scanf("%d",&f[i]); 
		dfs(1,-1);
		cout<<ans<<endl;
	}
	return 0;
	
	
}

C++11(clang++ 3.9) 解法, 执行用时: 640ms, 内存消耗: 94792K, 提交时间: 2020-05-31 23:20:39

#include<bits/stdc++.h>
using namespace std;

int ans,DP[1000005];
vector<int>R[1000005],W[1000005];
void DFS(int x,int fa)
{
	int i,j,m1=DP[x],m2=-2e9;
	for(i=0;i<R[x].size();i++)
	{
		j=R[x][i];
		if(j==fa)continue;
		DFS(j,x),m2=max(m2,DP[j]+W[x][i]);
		if(m1<m2)swap(m1,m2);
	}
	DP[x]=m1,ans=max(ans,m1+m2);
}
int main()
{
    int i,j,k,n,t; 
    scanf("%d",&t);
    while(t--)
    {
    	scanf("%d",&n),ans=-2e9;
    	for(i=1;i<=n;i++)R[i].clear(),W[i].clear();
    	for(i=2;i<=n;i++)
    	{
    		scanf("%d%d",&j,&k);
			R[i].push_back(j),R[j].push_back(i);
			W[i].push_back(k),W[j].push_back(k);
		}
		for(i=1;i<=n;i++)scanf("%d",&DP[i]);
		DFS(1,0);
		printf("%d\n",ans);
	}
}