P2986 [USACO10MAR] Great Cow Gathering G（换根dp）

思路:这题有一个树形dp中比较明显的特征. 1.无根树2.似乎父子关系并不是那么显然 考虑换根dp,虽然我们并不知道哪个点最优,但我们仍然能求解出以一个点为集合点的时候,其他点到这个集合点时的答案 然后,我们考虑利用求出来的这个点,维护父子关系,从而求出一个表 d p 2 ( u ) dp2(u) dp2(u)以 u u u为集合点时的答案. 不妨设 1 1 1为根,先求出其他点到1的答案是多少.以及1为根时的子树大小,对应的路径贡献 d p 1 ( u ) dp1(u) dp1(u) 接下来考虑换根dp。假设我们知道了以 u u u为集合点时,其他点到它的路径和 d p 2 ( u ) dp2(u) dp2(u).对于 u u u的儿子 v v v,有以下关系 d p 2 ( v ) = d p 2 ( u ) − ( s z [ v ] ∗ w ) + ( s u m − s z [ v ] ) ∗ w dp2(v)=dp2(u)-(sz[v]*w)+(sum-sz[v])*w dp2(v)=dp2(u)−(sz[v]∗w)+(sum−sz[v])∗w ( s u m − s z [ v ] ) ∗ w (sum-sz[v])*w (sum−sz[v])∗w代表了,父亲除了 v v v这个子树以外的所有点通过当前边走到了 v v v这个点,一共有 ( s u m − s z [ v ] ) (sum-sz[v]) (sum−sz[v])个牛,边权为 w w w.但由于 v v v不用再走向父亲了,故扣去 s z [ v ] ∗ w sz[v]*w sz[v]∗w的贡献。 总结:这是一类奇葩的树形dp。怎么说,就是让你求出一个点的解之后,根据解和解之间的父子关系（主要是兄弟的信息合并到父亲身上了）,然后更新儿子的一类dp。常常求出根的dp,再用根的dp值更新儿子

/*
Stairs upon the temple
I climb and I crawl in
People travel millions of miles just to see it
But they never conquer this way
*/
#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
ll dp1[maxn];ll sz[maxn];int a[maxn];
int n;ll sum=0;
void dfs1(int u,int fa){
	sz[u] = a[u];
	for(auto [v,w] : G[u]){
		if(v==fa) continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		dp1[u] += dp1[v] + sz[v]*w;
	}
}
ll dp2[maxn];
void dfs2(int u,int fa){
	for(auto [v,w] : G[u]){
		if(v==fa) continue;
		dp2[v] = dp2[u]+(sum-2*sz[v])*w;
		dfs2(v,u); 
	}
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i>a[i],sum+=a[i];
	for(int i=1;i>u>>v>>w;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	dfs1(1,0);
	dp2[1] = dp1[1];
	dfs2(1,0);
	ll ans = 1e15+7;
	for(int i=1;i