AT_abc409_e [ABC409E] Pair Annihilation

AT_abc409_e [ABC409E] Pair Annihilation

赛时没开longlong挂了。

思路

首先我们可以把这棵树转化为一颗有根树，且所有电子的都朝根节点移动。

那么接下来我们就需要选择一个最优的树根。

考虑换根dp。

但是可以发现换根时答案其实是没有变化的。

我们设 $f_i$ 表示以 $i$ 为根的子树电子全部集中到 $i$ 所耗费的能量，$g_i$ 表示以 $i$ 为根的子树电子全部集中到 $i$ 后的电子数量。

如图所示，我们设一号节点与二号节点之间的距离为 $v$，当我们要把根从 1 换到 2 时，相当于将原本要从 2 号节点移动到 1 号节点的电子留在 2 号，其他电子在 1 号节点，此时只有 1 号节点和 2 号节点存在电子。

我们设此时 1 号节点的电子数量（此处负电子数量算作负数）为 $a$，2 号节点的电子数量为 $b$，那么有 $a+b=0$ 且 $|a|=|b|$，那么此时无论我们把电子从 2 号节点移动到 1 号节点还是从 1 号节点移动到 2 号节点对答案产生的贡献是不变的，所以我们可以直接以任意节点为根跑dfs求出答案。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[100010],f[100010],g[100010];
struct N{ll y,v;
}; 
vector<N> e[100010];
void dfs(int x,int xfa){f[x]=0;g[x]=a[x];//g要初始化为当前节点电子数量 for(N y:e[x])if(y.y!=xfa){dfs(y.y,x);//遍历子节点 f[x]+=f[y.y]+abs(g[y.y])*y.v;//更新f g[x]+=g[y.y];//更新g }
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1,x,y,v;i<n;i++){cin>>x>>y>>v;e[x].push_back({y,v});//建树 e[y].push_back({x,v});}dfs(1,0);//dfs求f,g数组 cout<<f[1];//此处我们以1为根，所以输出f[1] return 0;
}