#include <bits/stdc++.h>
using namespace std;
const int kN = 1e5;
const int kLog = 16;
int n, timer, tin[1 + kN], tout[1 + kN], depth[1 + kN], anc[1 + kN][1 + kLog];
vector<int> g[1 + kN];
vector<tuple<int, int, int>> paths[1 + kN];
int64_t ans, aib[1 + kN], sum[1 + kN];
void maxSelf(int64_t &x, int64_t y) {
if (x < y) {
x = y;
}
}
void update(int64_t aib[], int x, int v) {
for (int i = x; i <= n; i += i & -i) {
aib[i] += v;
}
}
int64_t query(int64_t aib[], int x) {
int64_t ans = 0;
for (int i = x; i > 0; i = i & (i - 1)) {
ans += aib[i];
}
return ans;
}
int64_t query(int64_t aib[], int l, int r) {
return query(aib, r) - query(aib, l);
}
void dfs1(int u) {
tin[u] = ++timer;
for (int i = 1; i <= kLog; ++i) {
anc[u][i] = anc[anc[u][i - 1]][i - 1];
if (anc[u][i] == 0) {
break;
}
}
for (int v : g[u]) {
if (v != anc[u][0]) {
anc[v][0] = u;
depth[v] = depth[u] + 1;
dfs1(v);
}
}
tout[u] = timer;
}
int getLca(int u, int v) {
if (depth[u] < depth[v]) {
swap(u, v);
}
for (int i = kLog; i >= 0; --i) {
if (depth[u] - (1 << i) >= depth[v]) {
u = anc[u][i];
}
}
if (u == v) {
return u;
}
for (int i = kLog; i >= 0; --i) {
if (anc[u][i] != anc[v][i]) {
u = anc[u][i];
v = anc[v][i];
}
}
return anc[u][0];
}
int64_t dfs2(int u) {
int64_t sumChildren = 0, dp = 0;
for (int v : g[u]) {
if (v != anc[u][0]) {
int64_t ret = dfs2(v);
maxSelf(dp, ret);
sumChildren += ret;
}
}
update(sum, tin[u], sumChildren);
update(sum, tout[u] + 1, -sumChildren);
for (auto it : paths[u]) {
int p, q, w;
tie(p, q, w) = it;
maxSelf(dp, query(sum, tin[u], tin[p]) + query(sum, tin[u], tin[q]) + sumChildren + w
- query(aib, tin[u], tin[p]) - query(aib, tin[u], tin[q]));
}
update(aib, tin[u], dp);
update(aib, tout[u] + 1, -dp);
return dp;
}
void testCase() {
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
depth[1] = 1;
dfs1(1);
int m;
cin >> m;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
paths[getLca(u, v)].emplace_back(u, v, w);
}
cout << dfs2(1) << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tests = 1;
for (int tc = 0; tc < tests; ++tc) {
testCase();
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
5012 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5000 KB |
Output is correct |
2 |
Correct |
2 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
5156 KB |
Output is correct |
4 |
Correct |
98 ms |
29804 KB |
Output is correct |
5 |
Correct |
99 ms |
29724 KB |
Output is correct |
6 |
Correct |
87 ms |
29752 KB |
Output is correct |
7 |
Correct |
121 ms |
29724 KB |
Output is correct |
8 |
Correct |
100 ms |
29768 KB |
Output is correct |
9 |
Correct |
89 ms |
29744 KB |
Output is correct |
10 |
Correct |
135 ms |
29796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5000 KB |
Output is correct |
2 |
Correct |
2 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
5156 KB |
Output is correct |
4 |
Correct |
98 ms |
29804 KB |
Output is correct |
5 |
Correct |
99 ms |
29724 KB |
Output is correct |
6 |
Correct |
87 ms |
29752 KB |
Output is correct |
7 |
Correct |
121 ms |
29724 KB |
Output is correct |
8 |
Correct |
100 ms |
29768 KB |
Output is correct |
9 |
Correct |
89 ms |
29744 KB |
Output is correct |
10 |
Correct |
135 ms |
29796 KB |
Output is correct |
11 |
Correct |
11 ms |
5916 KB |
Output is correct |
12 |
Correct |
109 ms |
30008 KB |
Output is correct |
13 |
Correct |
112 ms |
30020 KB |
Output is correct |
14 |
Correct |
100 ms |
30108 KB |
Output is correct |
15 |
Correct |
101 ms |
30020 KB |
Output is correct |
16 |
Correct |
96 ms |
30100 KB |
Output is correct |
17 |
Correct |
115 ms |
30008 KB |
Output is correct |
18 |
Correct |
106 ms |
30132 KB |
Output is correct |
19 |
Correct |
107 ms |
30116 KB |
Output is correct |
20 |
Correct |
107 ms |
30020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
134 ms |
21496 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
5012 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
5012 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |