---
tags: IOI
---
# IOI2010 Day2-2 渋滞 (Traffic Congestion)

## 問題

https://www.ioi-jp.org/ioi/2010/tasks/tasks_jpn/day2/t2_traffic/index.html
https://oj.uz/problem/view/IOI10_traffic

木構造の都市と道路網があり、各都市には $P_i$ 人のホッケーファンが住んでいます。
都市の 1 つにホッケーの競技場を建てようとしています。
ホッケーの試合が終了すると、 一斉に都市 $i$ に向かって $P_i$ 人の人が帰りはじめ、渋滞が起こります。
最大の渋滞を最小化するにはどの都市に立てれば良いでしょうか？

## 考察

木の重心を知っていますか？
この問題は頂点に重みをつけたときの重心であることがわかります。
答えは重心のどちらかになるので、木DPをすると良いです。

## 実装

`std::reduce` はどこ…？

https://oj.uz/submission/254239

#include <bits/stdc++.h>
using namespace std;
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
 
 
int LocateCentre(int n, int p[], int s[], int d[]){
    const int sum = accumulate(p, p + n, 0);
    vector<vector<int>> g(n);
    for(int i = 0; i < n - 1; i++){
        const int a = s[i], b = d[i];
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> dp(n);
    auto dfs = [&](int from, int at, const auto& dfs) -> void {
        for(int i : g[at]) if(i != from){
            dfs(at, i, dfs);
            p[at] += p[i];
            chmax(dp[at], p[i]);
        }
        chmax(dp[at], sum - p[at]);
    };
    dfs(-1, 0, dfs);
    return min_element(dp.begin(), dp.end()) - dp.begin();
}