# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1263271 | DeltaStruct | Traffic (IOI10_traffic) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int res = 2e9;
int dfs(vector<vector<int>>& G,int x,int p,int s,vector<int>& A){
int m = 0,r = s-A[x]; for (int y:G[x]) if (y!=p){
int t = dfs(G,y,x,s,A); r -= t,m = max(m,t);
}
res = min(res,max(m,r));
return s-r;
}
int LocateCentre(int n,vector<int> A,vector<int> B,vector<int> C){
vector<vector<int>> G(n); for (int i(0);i < n-1;++i) G[B[i]].emplace_back(C[i]),G[C[i]].emplace_back(B[i]);
dfs(G,0,-1,accumulate(A.begin(),A.end(),0),A);
return res;
}