AtCoderBeginnerContest409の解説＆感想です。
コンテストリンク
問題一覧
- 【ABC409】A問題 - Conflict 考察から実装(c++)まで
- 【ABC409】B問題 - Citation 考察から実装(c++)まで
- 【ABC409】C問題 - Equilateral Triangle 考察から実装(c++)まで
- 【ABC409】D問題 - String Rotation 考察から実装(c++)まで
- 【ABC409】E問題 - Pair Annihilation 考察から実装(c++)まで <- イマココ
- 【ABC409】F問題 - Connecting Points 考察から実装(c++)まで
E問題 - Pair Annihilation
問題概要
$N$頂点の木が与えられる。変にはそれぞれ重み$w$がある。
それぞれの頂点には整数$x_i$が割り当てられていて、$0 < x_i$なら陽電子を$x_i$個、$x_i < 0$なら電子を$-x_i$個もっている。それぞれの電子は同じ頂点にある時打ち消し合う。
各電子・陽電子は木を好きに動くことができ、重さ$w$の辺を通る時にコスト$w$がかかる。
全ての電子を消すためにかかる最小コストを求めよ。
制約
- $ 2 \le N \le 10^5 $
- $ |x_i| \le 10^4 $
- $ \sum_{i=1}^{N}x_i = 0 $
- $ 0 \le w_i \le 10^4 $
考察
どこに注目すればいいのかイマイチ掴めない問題。「最小コストを求めよ」って言われてるのでとりあえず下界が知りたくなる。
そこで各辺に注目すると、その辺より左にある$x_i$の合計とその辺より右にある$x_i$の合計の絶対値は等しいはず。（等しくないと打ち消せないので）
ってことは、辺$i$に対して、端点以降の$x_i$の合計の絶対値を$s_i$とすると、$w_i \times s_i$のコストは最低でもかかるはず。てことは、$\sum_{i=1}^{M} w_i \times s_i$は下界となる。これが達成できてくれれば嬉しい。
これは葉に近い辺から順番に、「葉側に溜まっている電子・陽電子を根側にうつして辺を削除」をしていけば達成できる！
そしてそれは葉から順々に$s_i$を計算していけばいいので、DFSで求められる！
計算量はDFSで一回ずつ頂点を訪れるので、$O(N)$
実装
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
int main(void){
//入力
ll N;
cin>>N;
vll X(N);
for(int i=0;i<N;i++) cin>>X[i];
//nexts[i]が[{cost, i番目から行ける行き先}, {cost, 行き先},,,]となるように作る
vvpll nexts(N);
for(int i=0;i<N-1;i++){
ll u,v,w;
cin>>u>>v>>w;
nexts[u-1].push_back({w,v-1});
nexts[v-1].push_back({w,u-1});
}
//dfsで潜りながらs_iを計算してw_iとかけて答えに足していく
ll ans = 0;
function<ll(ll,ll,ll)> dfs = [&](ll now, ll parent, ll w){
ll ret = X[now];
for(pll next: nexts[now]){
if(next.second == parent) continue;
ret += dfs(next.second, now, next.first);
}
ans += abs(ret)*w;
return ret;
};
//頂点0を根としてDFS
dfs(0,-1,0);
cout<<ans<<endl;
return 0;
}