题意
题意:
+ 给出一颗n个点的树(1e5),每条边有一个权值c,
+ 每次操作可以令某个权值+1,
+ 求最少操作次数令根节点到每个叶节点路径上的权值和相等
思路
思路(构造):
+ 容易发现,越靠近根节点的,调整代价越小。
+ 我们可以把节点深度类比成距离,题目即为求把所有叶子节点调整到同一高度,每次优先调整靠近根部的。
+ 先dfs一遍更新到最远叶节点的距离dis[x],再循环一遍更新调整其余子节点的距离跟它一样。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e5+10;
struct node{int to,w;};
vector<node>G[maxn];
LL dis[maxn], ans;
void dfs(int x, int fa){
for(auto y : G[x]){
if(y.to==fa)continue;
dfs(y.to,x);
dis[x] = max(dis[x], dis[y.to]+y.w);//更新这棵子树根节点和最远叶子节点的距离
}
for(auto y : G[x]){
if(y.to==fa)continue;
ans += dis[x]-(dis[y.to]+y.w);//调整每个子节点到最远的距离,累加每次调整的代价
}
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, rt; cin>>n>>rt;
for(int i = 1; i < n; i++){
int x,y,z; cin>>x>>y>>z;
G[x].push_back(node{y,z});
G[y].push_back(node{x,z});
}
dfs(rt, 0);
cout<<ans<<"\n";
return 0;
}