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; }
