#include <bits/stdc++.h>
#define fi first
#define se second
#define pp pop_back
#define ll long long
#define pb push_back
#define ld long double
#define debug cout << "OK\n";
#define all(x) x.begin(), x.end()
#define mp make_pair
using namespace std;
const ll N = 1e6 + 200;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll pe = mod2;
const ll pe2 = 570210983;
const ld eps = 1e-6;
/*
Rucode: jaqVYNrpMj
JUDGE_ID: 295965SY
dl:160532
*/
void data() {
#ifdef NURS
freopen("main.in", "r", stdin);
freopen("main.out", "w", stdout);
#endif
}
int n, m, timer;
int tin[N], tout[N], up[20][N];
ll dp[N], dp2[N], l[N], r[N], w[N];
vector<int> g[N], g2[N];
struct fenw
{
ll f[N * 4];
void upd(int pos, int val)
{
for (int i = pos; i <= N; i = (i | (i + 1)))
f[i] += val;
}
ll sum(int pos)
{
ll res = 0;
for (int i = pos; i >= 1; i = (i & (i + 1)) - 1)
res += f[i];
return res;
}
ll get(int l, int r)
{
return sum(r) - sum(l - 1);
}
};
fenw tr, tr2;
void dfs(int v, int p)
{
tin[v] = ++timer;
up[0][v] = p;
for (int i = 1; i <= 20; i++)
up[i][v] = up[i - 1][up[i - 1][v]];
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (to == p)
continue;
dfs(to, v);
}
tout[v] = ++timer;
}
bool upper(int a, int b)
{
return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}
int lca(int a, int b)
{
if (upper(a, b))
return a;
if (upper(b, a))
return b;
for (int i = 20; i >= 0; i--)
{
if (up[i][a] && !upper(up[i][a], b))
a = up[i][a];
}
return up[0][a];
}
void dfs2(int v, int p)
{
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (to == p)
continue;
dfs2(to, v);
dp[v] += dp2[to];
}
dp2[v] = dp[v];
for (int i = 0; i < g2[v].size(); i++)
{
int pos = g2[v][i];
int a = l[pos], b = r[pos];
dp2[v] = max(dp2[v] , dp[v] + tr.get(tin[v], tin[a]) + tr.get(tin[v], tin[b])
- tr2.get(tin[v], tin[a]) - tr2.get(tin[v], tin[b]) + w[pos]);
}
tr.upd(tin[v], dp[v]);
tr.upd(tout[v], -dp[v]);
tr2.upd(tin[v], dp2[v]);
tr2.upd(tout[v], -dp2[v]);
}
int main()
{
data();
ios_base::sync_with_stdio(0),
cin.tie(0),cout.tie(0);
cin >> n;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u].pb(v), g[v].pb(u);
}
dfs(1, 0);
cin >> m;
for (int i = 1; i <= m; i++)
{
cin >> l[i] >> r[i] >> w[i];
int lc = lca(l[i], r[i]);
g2[lc].pb(i);
}
dfs2(1, 0);
cout << dp2[1];
}
Compilation message
election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int i = 0; i < g[v].size(); i++)
| ~~^~~~~~~~~~~~~
election_campaign.cpp: In function 'void dfs2(int, int)':
election_campaign.cpp:94:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i = 0; i < g[v].size(); i++)
| ~~^~~~~~~~~~~~~
election_campaign.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int i = 0; i < g2[v].size(); i++)
| ~~^~~~~~~~~~~~~~
election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:64:12: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
64 | up[i][v] = up[i - 1][up[i - 1][v]];
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:63:20: note: within this loop
63 | for (int i = 1; i <= 20; i++)
| ~~^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
47596 KB |
Output is correct |
2 |
Correct |
32 ms |
47596 KB |
Output is correct |
3 |
Correct |
36 ms |
47596 KB |
Output is correct |
4 |
Incorrect |
34 ms |
47852 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
47596 KB |
Output is correct |
2 |
Correct |
34 ms |
47708 KB |
Output is correct |
3 |
Correct |
33 ms |
47852 KB |
Output is correct |
4 |
Correct |
156 ms |
77164 KB |
Output is correct |
5 |
Correct |
149 ms |
77036 KB |
Output is correct |
6 |
Correct |
143 ms |
77164 KB |
Output is correct |
7 |
Correct |
145 ms |
77184 KB |
Output is correct |
8 |
Correct |
146 ms |
77036 KB |
Output is correct |
9 |
Correct |
143 ms |
77292 KB |
Output is correct |
10 |
Correct |
148 ms |
77036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
47596 KB |
Output is correct |
2 |
Correct |
34 ms |
47708 KB |
Output is correct |
3 |
Correct |
33 ms |
47852 KB |
Output is correct |
4 |
Correct |
156 ms |
77164 KB |
Output is correct |
5 |
Correct |
149 ms |
77036 KB |
Output is correct |
6 |
Correct |
143 ms |
77164 KB |
Output is correct |
7 |
Correct |
145 ms |
77184 KB |
Output is correct |
8 |
Correct |
146 ms |
77036 KB |
Output is correct |
9 |
Correct |
143 ms |
77292 KB |
Output is correct |
10 |
Correct |
148 ms |
77036 KB |
Output is correct |
11 |
Correct |
43 ms |
48900 KB |
Output is correct |
12 |
Correct |
156 ms |
77056 KB |
Output is correct |
13 |
Correct |
150 ms |
77044 KB |
Output is correct |
14 |
Correct |
150 ms |
77204 KB |
Output is correct |
15 |
Correct |
149 ms |
77036 KB |
Output is correct |
16 |
Correct |
146 ms |
77292 KB |
Output is correct |
17 |
Correct |
148 ms |
77036 KB |
Output is correct |
18 |
Correct |
148 ms |
77036 KB |
Output is correct |
19 |
Correct |
146 ms |
77164 KB |
Output is correct |
20 |
Correct |
154 ms |
77036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
242 ms |
68928 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
47596 KB |
Output is correct |
2 |
Correct |
32 ms |
47596 KB |
Output is correct |
3 |
Correct |
36 ms |
47596 KB |
Output is correct |
4 |
Incorrect |
34 ms |
47852 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
47596 KB |
Output is correct |
2 |
Correct |
32 ms |
47596 KB |
Output is correct |
3 |
Correct |
36 ms |
47596 KB |
Output is correct |
4 |
Incorrect |
34 ms |
47852 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |