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>
#define pb push_back
#define s second
#define f first
#define ll long long
#define pii pair<int,int>
#define left (node<<1),l,((l+r)>>1)
#define right ((node<<1)|1),((l+r)>>1) + 1,r
#define int ll
using namespace std;
const int N = 100005;
int cnt,a[N],d[25][N],dep[N],dp[N],in[N],out[N],fen[N];
vector <int> v[N];
set <pii> st;
vector <pair<pii,int> > vec[N];
void dfs(int x,int par){
dep[x] = dep[par] + 1;
in[x] = ++cnt;
d[0][x] = par;
for (int j = 0; j < v[x].size(); j++){
int to = v[x][j];
if (to != par) dfs(to,x);
}
out[x] = cnt;
}
void upd(int ind,int val){
while(ind <= N){
fen[ind] += val;
ind += (ind&(-ind));
}
}
int get(int ind){
int s=0;
while(ind){
s += fen[ind];
ind -= (ind&(-ind));
}
return s;
}
void solve(int x){
int S = 0;
for (int j = 0; j < v[x].size(); j++){
int to = v[x][j];
if (to == d[0][x]) continue;
solve(to);
S += dp[to];
}
dp[x] = S;
upd(in[x], S);
upd(in[x] + 1,-S);
st.clear(); st.insert({N,0});
for (int j = 0; j < v[x].size(); j++){
int to = v[x][j];
if (to == d[0][x]) continue;
st.insert({in[to],dp[to]});
}
for (int j = 0; j < vec[x].size(); j++){
int l = vec[x][j].f.f,r = vec[x][j].f.s;
int s = vec[x][j].s + S;
set <pii> :: iterator it;
if (l != x){
s += get(in[l]);
it = st.lower_bound({in[l],1e18});
it--;
s -= (it->s);
}
if (r != x){
s += get(in[r]);
it = st.lower_bound({in[r],1e18});
it--;
s -= (it->s);
}
dp[x] = max(dp[x],s);
}
for (int j = 0; j < v[x].size(); j++){
int to = v[x][j];
if (to == d[0][x]) continue;
S -= dp[to];
upd(in[to], S);
upd(out[to] + 1,-S);
S += dp[to];
}
}
int lca(int x,int y){
if (dep[x] > dep[y]) swap(x,y);
for (int j = 20; j >= 0; j--)
if (dep[d[j][y]] >= dep[x]) y = d[j][y];
if (x == y) return x;
for (int j = 20; j >= 0; j--)
if (d[j][x] != d[j][y]) x = d[j][x],y = d[j][y];
return d[0][x];
}
main (){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n;
cin>>n;
for (int i =1; i <n;i++){
int a,b;
cin>>a>>b;
v[a].pb(b),v[b].pb(a);
}
dfs(1,1);
for (int i = 1; i <= 20; i++)
for (int j = 1; j <= n; j++)
d[i][j] = d[i - 1][d[i - 1][j]];
int q;
cin>>q;
while(q--){
int x,y,z;
cin>>x>>y>>z;
int c = lca(x,y);
vec[c].pb({{x,y},z});
}
solve(1);
cout<<dp[1];
}
Compilation message (stderr)
election_campaign.cpp: In function 'void dfs(long long int, long long int)':
election_campaign.cpp:20:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (int j = 0; j < v[x].size(); j++){
| ~~^~~~~~~~~~~~~
election_campaign.cpp: In function 'void solve(long long int)':
election_campaign.cpp:42:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int j = 0; j < v[x].size(); j++){
| ~~^~~~~~~~~~~~~
election_campaign.cpp:53:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int j = 0; j < v[x].size(); j++){
| ~~^~~~~~~~~~~~~
election_campaign.cpp:59:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int j = 0; j < vec[x].size(); j++){
| ~~^~~~~~~~~~~~~~~
election_campaign.cpp:81:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int j = 0; j < v[x].size(); j++){
| ~~^~~~~~~~~~~~~
election_campaign.cpp: At global scope:
election_campaign.cpp:103:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
103 | main (){
| ^~~~
# | 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... |