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 MAXN = 1e5 + 10;
vector<int> grafo[MAXN],perguntas[MAXN];
int N,M,tab[MAXN][2],pai[MAXN],nivel[MAXN],ini[MAXN],fim[MAXN],dfsPtr,e1[MAXN],e2[MAXN],e3[MAXN];
void dfs_build(int v,int p){
pai[v] = p;
nivel[v] = nivel[p] + 1;
ini[v] = ++dfsPtr;
for(int u : grafo[v]){
if(u == p) continue;
dfs_build(u,v);
}
fim[v] = dfsPtr;
}
int LCA(int u,int v){
while(u != v){
if(nivel[u] < nivel[v]) swap(u,v);
u = pai[u];
}
return u;
}
int query_up(int v,int alvo){
int ans = 0;
if(v == alvo) return 0;
while(v != alvo){
ans += tab[v][0] - tab[v][1];
v = pai[v];
}
return ans;
}
void dfs_ans(int v,int p){
int temp0 = 0, best_delta = 0;
for(int u : grafo[v]){
if(u == p) continue;
dfs_ans(u,v);
temp0 += tab[u][1];
}
for(int i : perguntas[v]){
int u = e1[i],w = e2[i],x = e3[i];
//printf("LCA %d de %d %d com %d\n",v,u,w,x);
best_delta = max(best_delta, query_up(u,v) + query_up(w,v) + x );
}
tab[v][0] = temp0;
tab[v][1] = temp0 + best_delta;
//printf("V %d T0 %d BD %d\n",v,temp0,best_delta);
}
int main(){
scanf("%d",&N);
for(int i = 1;i<N;i++){
int u,v;
scanf("%d %d",&u,&v);
grafo[u].push_back(v);
grafo[v].push_back(u);
}
dfs_build(1,0);
scanf("%d",&M);
for(int i = 1;i<=M;i++){
scanf("%d %d %d",&e1[i],&e2[i],&e3[i]);
int ancestral = LCA(e1[i],e2[i]);
perguntas[ancestral].push_back(i);
}
dfs_ans(1,0);
printf("%d\n",max(tab[1][1],tab[1][0]));
return 0;
}
Compilation message (stderr)
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
~~~~~^~~~~~~~~
election_campaign.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&u,&v);
~~~~~^~~~~~~~~~~~~~~
election_campaign.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&M);
~~~~~^~~~~~~~~
election_campaign.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&e1[i],&e2[i],&e3[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |