# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
128200 | mirbek01 | Election Campaign (JOI15_election_campaign) | C++11 | 1061 ms | 30712 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
int n, m, a[N], b[N], c[N], dp[N];
int up[17][N], tin[N], tout[N], timer, ver[N];
vector <int> g[N], qe[N];
void dfs(int v, int pr){
tin[v] = ++ timer;
ver[timer] = v;
up[0][v] = pr;
for(int i = 1; i <= 16; i ++)
up[i][v] = up[i - 1][up[i - 1][v]];
for(int to : g[v]){
if(to == pr)
continue;
dfs(to, v);
}
tout[v] = timer;
}
bool upper(int a, int b){
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b){
if(upper(a, b))
return a;
if(upper(b, a))
return b;
for(int i = 16; i >= 0; i --){
if(!upper(up[i][a], b))
a = up[i][a];
}
return up[0][a];
}
void calc(int v, int pr){
for(int to : g[v]){
if(to == pr)
continue;
calc(to, v);
}
long long sum = 0;
for(int to : g[v]){
if(to == pr)
continue;
sum += dp[to];
}
dp[v] = sum;
for(int i = 0; i < qe[v].size(); i ++){
int id = qe[v][i];
int ret = c[id];
int vr = a[id];
while(vr != v){
if(up[0][vr] != v){
for(int to : g[ up[0][vr] ]){
if(to == up[1][vr] || to == vr)
continue;
ret += dp[to];
}
}
vr = up[0][vr];
}
vr = b[id];
while(vr != v){
if(up[0][vr] != v){
for(int to : g[ up[0][vr] ]){
if(to == up[1][vr] || to == vr)
continue;
ret += dp[to];
}
}
vr = up[0][vr];
}
for(int to : g[v]){
if(to == pr || upper(to, a[id]) || upper(to, b[id]))
continue;
ret += dp[to];
}
if(v != a[id]){
for(int to : g[ a[id] ]){
if(to == up[0][ a[id] ])
continue;
ret += dp[to];
}
}
if(v != b[id]){
for(int to : g[ b[id] ]){
if(to == up[0][ b[id] ])
continue;
ret += dp[to];
}
}
dp[v] = max(dp[v], ret);
}
}
int main(){
scanf("%d", &n);
for(int i = 1; i < n; i ++){
int u, v;
scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 1);
scanf("%d", &m);
for(int i = 1; i <= m; i ++){
scanf("%d %d %d", a+i, b+i, c+i);
qe[ lca(a[i], b[i]) ].push_back(i);
}
calc(1, 1);
cout << dp[1] << endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |