This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define in pair<int, int>
#define inn pair<int, in>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int MX = 1e5+5, LOGM = 18;
vector<int> adj[MX];
vector<inn> st[MX];
int tin[MX], tout[MX], pa[LOGM][MX], dp[MX];
int timer;
void dfs(int u, int p)
{
tin[u] = ++timer;
pa[0][u] = p;
for(int v: adj[u])
{
if(v==p)
continue;
dfs(v, u);
}
tout[u] = timer;
return;
}
int lca(int u, int v)
{
if(tin[u] >= tin[v])
swap(u, v);
if(tout[u] >= tout[v])
return u;
for(int i = LOGM-1; i >= 0; i--)
{
int k = pa[i][u];
if(tout[k] >= tout[v])
continue;
u = k;
}
return pa[0][u];
}
int fen[MX];
void add(int x, int val)
{
for(; x < MX; x+=(x&-x))
fen[x]+=val;
return;
}
int Q(int u)
{
int ret = 0;
for(int x = tin[u]; x; x-=(x&-x))
ret+=fen[x];
return ret;
}
void upd(int val, int u)
{
add(tin[u], val);
add(tout[u]+1, -val);
return;
}
void DFS(int u, int p)
{
int SUM = 0;
for(int v: adj[u])
{
if(v == p)
continue;
DFS(v, u);
SUM+=dp[v];
}
for(auto [C, ab]: st[u])
dp[u] = max(dp[u], C+Q(ab.f)+Q(ab.s));
dp[u]+=SUM;
upd(SUM-dp[u], u);
return;
}
signed main()
{
fast();
int n;
cin >> n;
int m = n-1;
while(m--)
{
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
pa[0][0] = 0; tin[0] = -1; tout[0] = INF;
dfs(1, 0);
for(int j = 1; j < LOGM; j++)
{
for(int i = 0; i <= n; i++)
pa[j][i] = pa[j-1][pa[j-1][i]];
}
int q; cin >> q;
while(q--)
{
int l, r, w;
cin >> l >> r >> w;
st[lca(l, r)].pb({w, {l, r}});
}
DFS(1, 0);
cout << dp[1] << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |