https://www.luogu.com.cn/problem/P2986
先说带点权的树重心做法：
https://blog.csdn.net/zstuyyyyccccbbbb/article/details/108558682树的重心的定义以及一些性质。
如果这个树有点权和边权怎么办？
关于边权：其实和所有边为单位1的重心一模一样。（网上搜了搜没怎么有比较详细的说明的，姑且当性质结论1）
关于点权：把”最大的子树节点数最少“改成“最大点权块最小”。
感性证明：
把这个问题转化成刚在关于边权的那个重心问题。去掉点权，也就是把有c[u]头牛的农场u拆成c[u]个牛数为1的农场。
那么发现，新拆出来的农场之间距离应该都是0，然后到其他一个农场的距离贡献都是一样的到该农场的边权。
这就类似建立了一个虚拟源点，这个源点到其他农场的距离等于每一个拆出来的农场的贡献和，而拆出来的农场彼此之间距离都为0.
那么此时这个图就变成了有好多边权为0和边权一致的比原来多了很多点的图。由结论1得重心和边权无关，和结点数有关，那么此时结点数变多，真实的重心应该由每一个节点的siz[i]=1结合而来，融汇到一起，就是这个虚拟源点(题目给的点）的c[i]。
由此点权将siz[i]=c[i]，然后由原来树的重心去求。
由于树的重心到每个点的距离和是最小的。求出来就是最终答案了。
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
LL n,sum=0,ans=0;
LL son[maxn],siz[maxn],dweight[maxn];
struct edge{LL to,w;
};
vector<edge>g[maxn];
void dfs(LL u,LL fa)
{siz[u]=dweight[u];for(LL i=0;i<g[u].size();i++){LL v=g[u][i].to;if(v==fa) continue;dfs(v,u);siz[u]+=siz[v];son[u]=max(son[u],siz[v]);}son[u]=max(son[u],sum-siz[u]);
}
void dfs2(LL u,LL fa,LL dis)
{
/// cout<<"g["<<u<<"]="<<g[u].size()<<endl;for(LL i=0;i<g[u].size();i++){LL to=g[u][i].to;if(to==fa) continue;cout<<u<<"---->"<<to<<endl;ans+=dweight[to]*(dis+g[u][i].w);
/// debug(ans);dfs2(to,u,dis+g[u][i].w);}
}
int main(void)
{cin.tie(0);std::ios::sync_with_stdio(false);cin>>n;for(LL i=1;i<=n;i++){cin>>dweight[i];sum+=dweight[i];}for(LL i=1;i<n;i++){LL u,v,c;cin>>u>>v>>c;g[u].push_back({v,c});g[v].push_back({u,c});}dfs(1,0);LL point=1;for(LL i=1;i<=n;i++){if(son[point]>son[i]){point=i;//带点权边权树的重心 }}/// cout<<"重心是"<<point<<endl;dfs2(point,-1,0);cout<<ans<<endl;
return 0;
}考虑换根dp。换根dp的一个比较显然的条件是可以o(n^2)暴力求每个点。这个题的暴力原题是https://www.luogu.com.cn/problem/P1364。可以暴力快乐过题。
那么换根dp先以任意一个点为根，求出以该点为根为的答案值。再通过这个点和父亲，节点的关系来更新。
先预处理出以1为根的答案dp[1]。
举例：以2为根的答案值为以2的父亲的答案值加上以(1为根的子树大小-以2为根的子树大小)*（1~2的边权)-以2为根的子树的子节点们要减去到以1为根的节点的多出来的（1~2)的边权。
文字表述有点长。换根dp建议画图比较容易理解。
表达式子： dp[v]=dp[u]+(siz[1]-2*siz[v])*g[u][i].w;
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
LL dp[maxn],siz[maxn],dis[maxn],c[maxn];
struct edge{LL to,w;
};
vector<edge>g[maxn];
void dfs1(LL u,LL fa)
{siz[u]=c[u];for(LL i=0;i<g[u].size();i++){LL v=g[u][i].to;if(v==fa) continue;dis[v]=dis[u]+g[u][i].w;//每个点到根节点的距离 dfs1(v,u);siz[u]+=siz[v];//以u为根的子树奶牛数量 }
}
void dfs2(LL u,LL fa)
{for(LL i=0;i<g[u].size();i++){LL v=g[u][i].to;if(v==fa) continue;dp[v]=dp[u]+(siz[1]-2*siz[v])*g[u][i].w;dfs2(v,u);}
}
int main(void)
{cin.tie(0);std::ios::sync_with_stdio(false);LL n;cin>>n;for(LL i=1;i<=n;i++) cin>>c[i];for(LL i=1;i<n;i++){LL u,v,w;cin>>u>>v>>w;g[u].push_back({v,w});g[v].push_back({u,w});}dfs1(1,-1);for(LL i=2;i<=n;i++){dp[1]+=dis[i]*c[i]; }dfs2(1,-1);LL ans=1e18;for(LL i=1;i<=n;i++) ans=min(ans,dp[i]);cout<<ans<<endl;
return 0;
}