#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define N 100001
typedef long long ll;
const long long MOD=1000000007;
using namespace std;
struct plan{
int x,y,votes;
};
int timer,m,n,l,k,sz[N],h[N],seg[N];
int tin[N],tout[N],up[N][20];
int in[N],out[N],tree[4*N+4];
vector<plan>path[N];
vector<int>adj[N];
void dfs(int node,int par=1){
tin[node]=++timer;
up[node][0]=par;
for(int i=1;i<=l;i++){
up[node][i]=up[up[node][i-1]][i-1];
}
sz[node]=1;
for(int x:adj[node]){
if(x!=par){
dfs(x,node);
sz[node]+=sz[x];
}
}
tout[node]=++timer;
}
void dfs1(int node,int par,int head){
seg[node]=++k;
h[node]=head;
pair<int,int>bigchild={0,-1};
for(int x:adj[node]){
if(x!=par) bigchild=max(bigchild,{sz[x],x});
}
if(bigchild.ss!=-1) dfs1(bigchild.ss,node,head);
for(int x:adj[node]){
if(x!=par && x!=bigchild.ss) dfs1(x,node,x);
}
}
bool is(int a,int b){
return (tin[a]<=tin[b] && tout[b]<=tout[a]);
}
int lca(int a,int b){
if(is(a,b)) return a;
if(is(b,a)) return b;
for(int i=l;i>=0;i--){
if(!is(up[a][i],b)) a=up[a][i];
}
return up[a][0];
}
int query(int id,int l,int r,int L,int R){
if(r<L || R<l) return 0;
if(L<=l && r<=R) return tree[id];
int m=(l+r)>>1;
return query(id*2,l,m,L,R)+query(id*2+1,m+1,r,L,R);
}
void update(int id,int l,int r,int x,int val){
if(l==r){
tree[id]=val;
return;
}
int m=(l+r)>>1;
if(m>=x) update(id*2,l,m,x,val);
else update(id*2+1,m+1,r,x,val);
tree[id]=tree[id*2]+tree[id*2+1];
}
int p(int a,int b){
if(is(h[a],b)) return query(1,1,k,seg[b],seg[a]);
return query(1,1,k,seg[h[a]],seg[a])+p(up[a][0],b);
}
void solve(int node,int par=1){
for(int x:adj[node]){
if(x!=par){
solve(x,node);
out[node]+=in[x];
in[node]=max(in[node],in[x]);
}
}
for(plan xx:path[node]){
int a=xx.x;
int b=xx.y;
int c=xx.votes;
// in[node]=max(in[node],p(a,node)+p(b,node)+c+out[node]);
while(a!=node){
c+=out[a];
c-=in[a];
a=up[a][0];
}
while(b!=node){
c+=out[a];
c-=in[a];
b=up[b][0];
}
c+=out[node];
in[node]=max(in[node],out[node]);
}
// update(1,1,k,seg[node],out[node]-in[node]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
l=ceil(log2(n));
for(int i=1;i<n;i++){
int a,b;
cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
dfs(1);
dfs1(1,1,1);
cin >> m;
while(m--){
int a,b,c;
cin >> a >> b >> c;
int x=lca(a,b);
path[x].pb({a,b,c});
}
solve(1);
cout << in[1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
208 ms |
20644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
