#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
const int LOG = 20;
int n, m;
vector<int> g[maxn];
int dep[maxn];
int par[maxn][LOG+1];
vector<int> leaves[maxn];
ll dp0[maxn]; // no path goes direct thru me
ll dp1[maxn]; // path goes directly thru me
vector<ll> dp[maxn]; // no path thru me, and no path thru ith leaf
void gen(int at, int p) {
for (int j=1; j<LOG; j++) {
par[at][j] = par[par[at][j-1]][j-1];
}
for (int to: g[at]) {
if (to==p) continue;
leaves[at].push_back(to);
par[to][0]=at;
dep[to]=1+dep[at];
gen(to,at);
}
}
int lca(int x, int y) {
if (dep[x]<dep[y]) swap(x,y);
int dx=dep[x]-dep[y];
for (int j=0; j<LOG; j++) {
if (dx>>j&1) {
x=par[x][j];
}
}
if (x==y) return x;
for (int j=LOG-1; j>=0; j--) {
if (par[x][j] != par[y][j]) {
x=par[x][j];
y=par[y][j];
}
}
return par[x][0];
}
int a[maxn], b[maxn];
ll c[maxn];
vector<int> qu[maxn];
void procQuery(int i) {
int from = a[i];
int to = b[i];
int mid = lca(from, to);
qu[mid].push_back(i);
}
void dfs(int at) {
for (int to: leaves[at]) {
dfs(to);
dp0[at] += max(dp0[to], dp1[to]);
}
int lcount = leaves[at].size();
dp[at].resize(lcount);
// ith leaf is banned
for (int i=0; i<lcount; i++) {
for (int j=0; j<lcount; j++) {
if (i == j) continue;
int to = leaves[at][j];
dp[at][i] += max(dp0[to], dp1[to]);
}
}
for (int qi: qu[at]) {
vector<vector<int>> paths;
// get paths a->at and at<-b
for (int nd: {a[qi],b[qi]}) {
if (nd==at) continue;
vector<int> path = {nd};
while (par[nd][0] != at) {
nd=par[nd][0];
path.push_back(nd);
}
reverse(path.begin(), path.end());
paths.push_back(path);
}
ll cur = c[qi];
for (int to: leaves[at]) {
int id=-1;
for (int j=0; j<int(paths.size()); j++) {
if (paths[j].front() == to) {
id = j;
}
}
// at->to->...a
if (~id) {
auto &p = paths[id];
int plen = p.size();
for (int j=0; j<plen; j++) {
if (j==plen-1) {
int end = p[j];
cur += dp0[end];
} else {
int nid=0;
while (leaves[p[j]][nid] != p[j+1]) nid++;
cur += dp[p[j]][nid];
}
}
} else {
cur += max(dp0[to],dp1[to]);
}
}
dp1[at] = max(dp1[at], cur);
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n;
for (int i=0; i<n-1; i++) {
int u,v;
cin>>u>>v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
gen(0,0);
cin>>m;
for (int i=0; i<m; i++) {
cin>>a[i]>>b[i]>>c[i];
--a[i];
--b[i];
procQuery(i);
}
dfs(0);
ll res = max(dp0[0], dp1[0]);
cout<<res<<endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
67 ms |
94296 KB |
Output is correct |
2 |
Correct |
63 ms |
94304 KB |
Output is correct |
3 |
Correct |
67 ms |
94328 KB |
Output is correct |
4 |
Correct |
73 ms |
94584 KB |
Output is correct |
5 |
Correct |
206 ms |
111480 KB |
Output is correct |
6 |
Correct |
151 ms |
135072 KB |
Output is correct |
7 |
Correct |
255 ms |
126024 KB |
Output is correct |
8 |
Execution timed out |
1100 ms |
108408 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
94328 KB |
Output is correct |
2 |
Correct |
64 ms |
94328 KB |
Output is correct |
3 |
Correct |
66 ms |
94712 KB |
Output is correct |
4 |
Execution timed out |
1088 ms |
138028 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
94328 KB |
Output is correct |
2 |
Correct |
64 ms |
94328 KB |
Output is correct |
3 |
Correct |
66 ms |
94712 KB |
Output is correct |
4 |
Execution timed out |
1088 ms |
138028 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
567 ms |
112996 KB |
Output is correct |
2 |
Execution timed out |
1062 ms |
138580 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
67 ms |
94296 KB |
Output is correct |
2 |
Correct |
63 ms |
94304 KB |
Output is correct |
3 |
Correct |
67 ms |
94328 KB |
Output is correct |
4 |
Correct |
73 ms |
94584 KB |
Output is correct |
5 |
Correct |
206 ms |
111480 KB |
Output is correct |
6 |
Correct |
151 ms |
135072 KB |
Output is correct |
7 |
Correct |
255 ms |
126024 KB |
Output is correct |
8 |
Execution timed out |
1100 ms |
108408 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
67 ms |
94296 KB |
Output is correct |
2 |
Correct |
63 ms |
94304 KB |
Output is correct |
3 |
Correct |
67 ms |
94328 KB |
Output is correct |
4 |
Correct |
73 ms |
94584 KB |
Output is correct |
5 |
Correct |
206 ms |
111480 KB |
Output is correct |
6 |
Correct |
151 ms |
135072 KB |
Output is correct |
7 |
Correct |
255 ms |
126024 KB |
Output is correct |
8 |
Execution timed out |
1100 ms |
108408 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |