树形dp

实在太菜了，之前做过的模板还是给忘记了，wa10000次才刻骨铭心。

#include<iostream>
#include<cstring>
using namespace std;
const    int N=200010;
typedef long long ll;
int h[N],ne[N],w[N],idx,e[N];
int n;
ll ans=-1e18;
void add(int a,int b)
{
   
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
ll dfs(int u,int fa)
{
   
	ll d1=0,d2=0;
	for(int i=h[u];~i;i=ne[i])
	{
   
		int j=e[i];
		if(j==fa)	continue;
		ll t=dfs(j,u);
		if(t>=d1)	d2=d1,d1=t;
		else if(t>d2)	d2=t;
	}	
	ans=max(ans,d1+d2+w[u]);  //把ans当做一个全局变量来存
	return d1+w[u];     //犯错了，，之前写的return整条链了，应该return底下的最大值
 } 
int main()
{
   
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
        memset(h,-1,sizeof h);
        for(int i=1;i<=n-1;i++)
        {
   
        	int a,b;
        	scanf("%d%d",&a,&b);
        	add(a,b);
        	add(b,a);
		}
    dfs(1,-1);
    printf("%lld\n",ans);
    return 0;
}