#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 1000004
#define INF 1e9+7
using namespace std;
ll n,m,x,y,a[N],b[N],c[N],depth[N],dp[N][30],tin[N],tout[N],countt,ans[N];
ll pedia[N],seg[4*N],lazy[4*N];
vector < vector < ll > > graph(N);
vector < vector < ll > > queries(N);
void init(ll cur,ll par)
{
dp[cur][0] = par;
depth[cur] = depth[par] + 1;
tin[cur] = countt++;
rep(i,0,graph[cur].size())
{
if(graph[cur][i] == par)
continue;
init(graph[cur][i],cur);
}
tout[cur] = countt++;
return;
}
ll jump(ll cur,ll i)
{
if(dp[cur][i])
return dp[cur][i];
return dp[cur][i] = jump(jump(cur,i-1),i-1);
}
bool isancestor(ll i,ll j)
{
return (tin[i] <= tin[j] && tout[i] >= tout[j]);
}
ll lca(ll i,ll j)
{
if(isancestor(i,j))
return i;
if(isancestor(j,i))
return j;
for(int p = 29;p >= 0;p--)
{
if(!isancestor(jump(i,p),j))
{
i = jump(i,p);
}
}
return jump(i,0);
}
void relax(ll low,ll high,ll pos)
{
if(lazy[pos])
{
seg[pos] += lazy[pos];
if(low != high)
{
lazy[pos*2+1] += lazy[pos];
lazy[pos*2+2] += lazy[pos];
}
lazy[pos] = 0;
}
return;
}
void update(ll low,ll high,ll pos,ll slow,ll shigh,ll val)
{
relax(low,high,pos);
if(low >= slow && high <= shigh)
{
seg[pos] += val;
if(low != high)
{
lazy[pos*2+1] += val;
lazy[pos*2+2] += val;
}
return;
}
if(low > shigh || high < slow)
return;
ll mid = (low+high)/2;
update(low,mid,pos*2+1,slow,shigh,val);
update(mid+1,high,pos*2+2,slow,shigh,val);
seg[pos] = seg[pos*2+1]+seg[pos*2+2];
return;
}
ll query(ll low,ll high,ll pos,ll slow)
{
relax(low,high,pos);
if(low == high && low == slow)
{
return seg[pos];
}
if(low > slow || high < slow)
return 0;
ll mid = (low+high)/2;
return query(low,mid,pos*2+1,slow)+query(mid+1,high,pos*2+2,slow);
}
ll solve(ll cur,ll par)
{
if(ans[cur] != -1)
return ans[cur];
ll res = 0;
rep(i,0,graph[cur].size())
{
if(graph[cur][i] == par)
continue;
pedia[cur] += solve(graph[cur][i],cur);
}
rep(i,0,graph[cur].size())
{
if(graph[cur][i] == par)
continue;
ll v = graph[cur][i];
update(0,countt,0,tin[v],tout[v],pedia[cur] - ans[v]);
}
res = pedia[cur];
rep(i,0,queries[cur].size())
{
ll j = queries[cur][i];
ll cand = -pedia[cur] + pedia[a[j]] + pedia[b[j]] + c[j];
cand += query(0,countt,0,tin[a[j]]);
cand += query(0,countt,0,tin[b[j]]);
//cout << cur << " " << j << " " << pedia[cur] << " "<< c[j] << " "<<query(0,countt,0,tin[a[j]]) << " " << ans[a[j]] << " "<<cand << "\n";
res = max(res,cand);
}
//cout << cur << " " << res << "\n";
return ans[cur] = res;
}
int main()
{
// ios_base::sync_with_stdio(false);
cin >> n;
rep(i,0,n-1)
{
cin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
init(1,1);
cin >> m;
rep(i,0,m)
{
cin >> a[i] >> b[i] >> c[i];
queries[lca(a[i],b[i])].push_back(i);
}
memset(ans,-1,sizeof ans);
cout << solve(1,1) << endl;
return 0;
}
Compilation message
election_campaign.cpp: In function 'void init(long long int, long long int)':
election_campaign.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i = a;i < b;i++)
election_campaign.cpp:30:9:
rep(i,0,graph[cur].size())
~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:30:5: note: in expansion of macro 'rep'
rep(i,0,graph[cur].size())
^~~
election_campaign.cpp: In function 'long long int solve(long long int, long long int)':
election_campaign.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i = a;i < b;i++)
election_campaign.cpp:144:9:
rep(i,0,graph[cur].size())
~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:144:5: note: in expansion of macro 'rep'
rep(i,0,graph[cur].size())
^~~
election_campaign.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i = a;i < b;i++)
election_campaign.cpp:152:9:
rep(i,0,graph[cur].size())
~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:152:5: note: in expansion of macro 'rep'
rep(i,0,graph[cur].size())
^~~
election_campaign.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i = a;i < b;i++)
election_campaign.cpp:163:9:
rep(i,0,queries[cur].size())
~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:163:5: note: in expansion of macro 'rep'
rep(i,0,queries[cur].size())
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
55288 KB |
Output is correct |
2 |
Correct |
53 ms |
55288 KB |
Output is correct |
3 |
Correct |
54 ms |
55160 KB |
Output is correct |
4 |
Correct |
56 ms |
55672 KB |
Output is correct |
5 |
Correct |
314 ms |
94184 KB |
Output is correct |
6 |
Correct |
268 ms |
99076 KB |
Output is correct |
7 |
Correct |
327 ms |
97764 KB |
Output is correct |
8 |
Correct |
281 ms |
92920 KB |
Output is correct |
9 |
Correct |
334 ms |
96872 KB |
Output is correct |
10 |
Correct |
278 ms |
92852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
55160 KB |
Output is correct |
2 |
Correct |
54 ms |
55208 KB |
Output is correct |
3 |
Correct |
56 ms |
55672 KB |
Output is correct |
4 |
Correct |
478 ms |
101940 KB |
Output is correct |
5 |
Correct |
483 ms |
102112 KB |
Output is correct |
6 |
Correct |
471 ms |
101980 KB |
Output is correct |
7 |
Correct |
487 ms |
102256 KB |
Output is correct |
8 |
Correct |
467 ms |
102256 KB |
Output is correct |
9 |
Correct |
456 ms |
102272 KB |
Output is correct |
10 |
Correct |
478 ms |
102136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
55160 KB |
Output is correct |
2 |
Correct |
54 ms |
55208 KB |
Output is correct |
3 |
Correct |
56 ms |
55672 KB |
Output is correct |
4 |
Correct |
478 ms |
101940 KB |
Output is correct |
5 |
Correct |
483 ms |
102112 KB |
Output is correct |
6 |
Correct |
471 ms |
101980 KB |
Output is correct |
7 |
Correct |
487 ms |
102256 KB |
Output is correct |
8 |
Correct |
467 ms |
102256 KB |
Output is correct |
9 |
Correct |
456 ms |
102272 KB |
Output is correct |
10 |
Correct |
478 ms |
102136 KB |
Output is correct |
11 |
Correct |
90 ms |
56824 KB |
Output is correct |
12 |
Correct |
500 ms |
102128 KB |
Output is correct |
13 |
Correct |
500 ms |
102136 KB |
Output is correct |
14 |
Correct |
477 ms |
102236 KB |
Output is correct |
15 |
Correct |
486 ms |
102264 KB |
Output is correct |
16 |
Correct |
488 ms |
102264 KB |
Output is correct |
17 |
Correct |
489 ms |
102288 KB |
Output is correct |
18 |
Correct |
488 ms |
102184 KB |
Output is correct |
19 |
Correct |
483 ms |
102404 KB |
Output is correct |
20 |
Correct |
486 ms |
102388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
554 ms |
97956 KB |
Output is correct |
2 |
Correct |
481 ms |
104388 KB |
Output is correct |
3 |
Correct |
700 ms |
102816 KB |
Output is correct |
4 |
Correct |
545 ms |
98944 KB |
Output is correct |
5 |
Correct |
651 ms |
102600 KB |
Output is correct |
6 |
Correct |
518 ms |
98476 KB |
Output is correct |
7 |
Correct |
695 ms |
102316 KB |
Output is correct |
8 |
Correct |
565 ms |
100088 KB |
Output is correct |
9 |
Correct |
470 ms |
104440 KB |
Output is correct |
10 |
Correct |
689 ms |
101744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
55288 KB |
Output is correct |
2 |
Correct |
53 ms |
55288 KB |
Output is correct |
3 |
Correct |
54 ms |
55160 KB |
Output is correct |
4 |
Correct |
56 ms |
55672 KB |
Output is correct |
5 |
Correct |
314 ms |
94184 KB |
Output is correct |
6 |
Correct |
268 ms |
99076 KB |
Output is correct |
7 |
Correct |
327 ms |
97764 KB |
Output is correct |
8 |
Correct |
281 ms |
92920 KB |
Output is correct |
9 |
Correct |
334 ms |
96872 KB |
Output is correct |
10 |
Correct |
278 ms |
92852 KB |
Output is correct |
11 |
Correct |
57 ms |
55672 KB |
Output is correct |
12 |
Correct |
56 ms |
55672 KB |
Output is correct |
13 |
Correct |
56 ms |
55672 KB |
Output is correct |
14 |
Correct |
56 ms |
55672 KB |
Output is correct |
15 |
Correct |
57 ms |
55564 KB |
Output is correct |
16 |
Correct |
56 ms |
55628 KB |
Output is correct |
17 |
Correct |
57 ms |
55672 KB |
Output is correct |
18 |
Correct |
56 ms |
55656 KB |
Output is correct |
19 |
Correct |
56 ms |
55580 KB |
Output is correct |
20 |
Correct |
60 ms |
55672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
55288 KB |
Output is correct |
2 |
Correct |
53 ms |
55288 KB |
Output is correct |
3 |
Correct |
54 ms |
55160 KB |
Output is correct |
4 |
Correct |
56 ms |
55672 KB |
Output is correct |
5 |
Correct |
314 ms |
94184 KB |
Output is correct |
6 |
Correct |
268 ms |
99076 KB |
Output is correct |
7 |
Correct |
327 ms |
97764 KB |
Output is correct |
8 |
Correct |
281 ms |
92920 KB |
Output is correct |
9 |
Correct |
334 ms |
96872 KB |
Output is correct |
10 |
Correct |
278 ms |
92852 KB |
Output is correct |
11 |
Correct |
53 ms |
55160 KB |
Output is correct |
12 |
Correct |
54 ms |
55208 KB |
Output is correct |
13 |
Correct |
56 ms |
55672 KB |
Output is correct |
14 |
Correct |
478 ms |
101940 KB |
Output is correct |
15 |
Correct |
483 ms |
102112 KB |
Output is correct |
16 |
Correct |
471 ms |
101980 KB |
Output is correct |
17 |
Correct |
487 ms |
102256 KB |
Output is correct |
18 |
Correct |
467 ms |
102256 KB |
Output is correct |
19 |
Correct |
456 ms |
102272 KB |
Output is correct |
20 |
Correct |
478 ms |
102136 KB |
Output is correct |
21 |
Correct |
90 ms |
56824 KB |
Output is correct |
22 |
Correct |
500 ms |
102128 KB |
Output is correct |
23 |
Correct |
500 ms |
102136 KB |
Output is correct |
24 |
Correct |
477 ms |
102236 KB |
Output is correct |
25 |
Correct |
486 ms |
102264 KB |
Output is correct |
26 |
Correct |
488 ms |
102264 KB |
Output is correct |
27 |
Correct |
489 ms |
102288 KB |
Output is correct |
28 |
Correct |
488 ms |
102184 KB |
Output is correct |
29 |
Correct |
483 ms |
102404 KB |
Output is correct |
30 |
Correct |
486 ms |
102388 KB |
Output is correct |
31 |
Correct |
554 ms |
97956 KB |
Output is correct |
32 |
Correct |
481 ms |
104388 KB |
Output is correct |
33 |
Correct |
700 ms |
102816 KB |
Output is correct |
34 |
Correct |
545 ms |
98944 KB |
Output is correct |
35 |
Correct |
651 ms |
102600 KB |
Output is correct |
36 |
Correct |
518 ms |
98476 KB |
Output is correct |
37 |
Correct |
695 ms |
102316 KB |
Output is correct |
38 |
Correct |
565 ms |
100088 KB |
Output is correct |
39 |
Correct |
470 ms |
104440 KB |
Output is correct |
40 |
Correct |
689 ms |
101744 KB |
Output is correct |
41 |
Correct |
57 ms |
55672 KB |
Output is correct |
42 |
Correct |
56 ms |
55672 KB |
Output is correct |
43 |
Correct |
56 ms |
55672 KB |
Output is correct |
44 |
Correct |
56 ms |
55672 KB |
Output is correct |
45 |
Correct |
57 ms |
55564 KB |
Output is correct |
46 |
Correct |
56 ms |
55628 KB |
Output is correct |
47 |
Correct |
57 ms |
55672 KB |
Output is correct |
48 |
Correct |
56 ms |
55656 KB |
Output is correct |
49 |
Correct |
56 ms |
55580 KB |
Output is correct |
50 |
Correct |
60 ms |
55672 KB |
Output is correct |
51 |
Correct |
696 ms |
100448 KB |
Output is correct |
52 |
Correct |
497 ms |
104568 KB |
Output is correct |
53 |
Correct |
713 ms |
102036 KB |
Output is correct |
54 |
Correct |
521 ms |
99348 KB |
Output is correct |
55 |
Correct |
593 ms |
100056 KB |
Output is correct |
56 |
Correct |
494 ms |
104512 KB |
Output is correct |
57 |
Correct |
684 ms |
102656 KB |
Output is correct |
58 |
Correct |
550 ms |
99372 KB |
Output is correct |
59 |
Correct |
588 ms |
100396 KB |
Output is correct |
60 |
Correct |
494 ms |
104544 KB |
Output is correct |
61 |
Correct |
662 ms |
102776 KB |
Output is correct |
62 |
Correct |
545 ms |
99232 KB |
Output is correct |
63 |
Correct |
665 ms |
100088 KB |
Output is correct |
64 |
Correct |
488 ms |
104644 KB |
Output is correct |
65 |
Correct |
710 ms |
102384 KB |
Output is correct |
66 |
Correct |
511 ms |
99104 KB |
Output is correct |
67 |
Correct |
605 ms |
100092 KB |
Output is correct |
68 |
Correct |
489 ms |
104640 KB |
Output is correct |
69 |
Correct |
668 ms |
101868 KB |
Output is correct |
70 |
Correct |
544 ms |
98476 KB |
Output is correct |