肥宅快乐树是一棵神秘而巨大的树，它长有许多枝条和节点，每条枝连接树中两个节点，每个节点上都长有一瓶肥宅快乐水。 何老板是肥宅快乐水的资深爱好者。历经艰难，他终于找到了这棵传说中的快乐树。他想要获取树上所有的快乐水，迫不及待地想从树根往树上爬。 每经过一条树枝都会耗费一定体力。而且快乐树自带防御功能，即每条枝上都有一个一次性陷阱，一旦踏上该枝，何老板就会被立即弹射回地面，他得重新从根往上爬。 （注1：一次性陷阱是指，陷阱只在第一次经过该枝时有效） （注2：从i号点回到i的父亲节点，不耗费体力） 每个节点上都有开有一些肥宅快乐花，花的香气可以让何老板经过当前节点所连的树枝时，耗费的体力值减少。不同节点的快乐花数量不一，产生的减少体力消耗的效果也不一定相同。 何老板发现快乐树还有一个神秘“换根”功能。何老板可以将指定节点变换为树根，变换后，树中树枝连接情况保持不变。但是只能进行一次换根操作。 快乐树共n个节点，编号1到n，开始时1号点为根。 何老板想知道，以哪个节点为根才能使他收集齐n瓶快乐水耗费的总体力最少。请你帮你计算。
解
发现每条边都经过儿子节点的size值
换根的话只有一条边的贡献改变
考虑换根的话 可以dfs 也可以树形DP 以子树为状态
code:
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define maxnn 1000010
#define ll long long
int n;
ll las[maxnn],en[maxnn],le[maxnn],tot,nex[maxnn];
ll size[maxnn],w[maxnn];
int mark[maxnn];
ll ans=0;
ll root=1;
ll cnt=0;
ll aass=0;
ll pos=0;
void add(int a,int b,ll c)
{
en[++tot]=b;
nex[tot]=las[a];
las[a]=tot;
le[tot]=c;
}
void dfs1(int v,int fa)
{
size[v]=1;
for(int i=las[v];i;i=nex[i])
{
int u=en[i];
if(u!=fa)
{
dfs1(u,v);
size[v]+=size[u];
}
}
}
void dfs2(int v,int fa)
{
for(int i=las[v];i;i=nex[i])
{
int u=en[i];
if(u!=fa)
{
ans=ans+le[i]*size[u]-size[u]*w[v];
dfs2(u,v);
}
}
}
void huan(int v,int fa)
{
for(int i=las[v];i;i=nex[i])
{
int u=en[i];
if(u!=fa&&(!mark[u]))
{
int tmp1=size[v]-size[u];
int tmp2=size[v];
int tmp3=size[u];
mark[u]=1;
ans=ans-le[i]*size[u]+size[u]*w[v]+(size[v]-size[u])*(le[i]-w[u]);
size[u]=size[u]+tmp1;
size[v]=tmp1;
if(aass>ans)
{
pos=u;
aass=ans;
}
huan(u,v);
ans=ans+le[i]*tmp3-tmp3*w[v]-(tmp2-tmp3)*(le[i]-w[u]);
size[v]=tmp2;
size[u]=tmp3;
}
}
}
int main()
{
//freopen("happytree.in","r",stdin);
//freopen("happytree.out","w",stdout);
ll x,y,z;
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%lld",&w[i]);
}
for(int i=1;i<n;i++)
{
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs1(1,1);
pos=1;
dfs2(1,1);
aass=ans;mark[1]=1;
huan(root,root);
cout<<pos<<endl;
cout<<aass<<endl;
}