#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pi pair<int, int>
#define pb push_back
constexpr int LIM = 1e5;
vector<int>g[LIM + 10];
int pre[LIM + 10];
int post[LIM + 10];
int nxt[LIM + 10][18];
int dp[LIM + 10][2];
vector<pair<pi, pi> >zap[LIM + 10];
bool czy(int a, int b) {
return pre[a] <= pre[b] && post[a] >= post[b];
}
pi lca(int a, int b) {
if(pre[a] <= pre[b]) {
swap(a, b);
}
for(int i = 17; i >= 0; i--) {
if(!czy(nxt[a][i], b)) {
a = nxt[a][i];
}
}
return {a, nxt[a][0]};
}
int aktpre = 1, aktpost = 1;
void dfs(int v, int o) {
pre[v] = aktpre++;
nxt[v][0] = o;
for(int i = 1; i <= 17; i++) {
nxt[v][i] = nxt[nxt[v][i - 1]][i - 1];
}
for(auto x : g[v]) {
if(x != o) {
dfs(x, v);
}
}
post[v] = aktpost++;
}
void cntdp(int v, int o) {
int sum = 0;
for(auto x : g[v]) {
if(x != o) {
cntdp(x, v);
sum += max(dp[x][0], dp[x][1]);
}
}
dp[v][0] = sum;
for(auto x : zap[v]) {
if(x.nd.st == v) {
dp[v][1] = max(dp[v][1], sum - max(dp[x.st.nd][0], dp[x.st.nd][1]) + dp[x.nd.nd][0] + x.st.st);
}
else if(x.nd.nd == v) {
dp[v][1] = max(dp[v][1], sum - max(dp[x.st.nd][0], dp[x.st.nd][1]) + dp[x.nd.st][0] + x.st.st);
}
else {
dp[v][1] = max(dp[v][1], sum - max(dp[x.st.nd][0], dp[x.st.nd][1]) + dp[x.nd.nd][0] + dp[x.nd.st][0] + x.st.st);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, 1);
int t;
cin >> t;
for(int i = 1; i <= t; i++) {
int a, b, x;
cin >> a >> b >> x;
pi tmp = lca(a, b);
zap[tmp.nd].pb({{x, tmp.st}, {a, b}});
}
cntdp(1, 1);
cout << max(dp[1][0], dp[1][1]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4948 KB |
Output is correct |
3 |
Incorrect |
4 ms |
5028 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
4 ms |
5204 KB |
Output is correct |
4 |
Correct |
117 ms |
29492 KB |
Output is correct |
5 |
Correct |
124 ms |
29528 KB |
Output is correct |
6 |
Correct |
106 ms |
29508 KB |
Output is correct |
7 |
Correct |
118 ms |
29476 KB |
Output is correct |
8 |
Correct |
119 ms |
29588 KB |
Output is correct |
9 |
Correct |
109 ms |
29608 KB |
Output is correct |
10 |
Correct |
108 ms |
29516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
4 ms |
5204 KB |
Output is correct |
4 |
Correct |
117 ms |
29492 KB |
Output is correct |
5 |
Correct |
124 ms |
29528 KB |
Output is correct |
6 |
Correct |
106 ms |
29508 KB |
Output is correct |
7 |
Correct |
118 ms |
29476 KB |
Output is correct |
8 |
Correct |
119 ms |
29588 KB |
Output is correct |
9 |
Correct |
109 ms |
29608 KB |
Output is correct |
10 |
Correct |
108 ms |
29516 KB |
Output is correct |
11 |
Correct |
14 ms |
6100 KB |
Output is correct |
12 |
Correct |
133 ms |
29740 KB |
Output is correct |
13 |
Correct |
127 ms |
29848 KB |
Output is correct |
14 |
Correct |
119 ms |
29916 KB |
Output is correct |
15 |
Correct |
137 ms |
29820 KB |
Output is correct |
16 |
Correct |
119 ms |
29980 KB |
Output is correct |
17 |
Correct |
111 ms |
29848 KB |
Output is correct |
18 |
Correct |
115 ms |
29856 KB |
Output is correct |
19 |
Correct |
117 ms |
29860 KB |
Output is correct |
20 |
Correct |
111 ms |
29804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
123 ms |
21280 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4948 KB |
Output is correct |
3 |
Incorrect |
4 ms |
5028 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4948 KB |
Output is correct |
3 |
Incorrect |
4 ms |
5028 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |