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>
#define fs first
#define sn second
#define mp make_pair
#define N 100100
using namespace std;
ll n,m,ans,x,y,z,w,tot,h[N],f[N],sz[N],hs[N],top[N],fa[N],dep[N],dfn[N],low[N],v[N];
vector<pair<pair<ll,ll>,ll> >d[N];
struct rec
{
ll to,nx;
}e[N<<1];
void addl(ll x,ll y)
{
e[++tot].to=y;
e[tot].nx=h[x];
h[x]=tot;
return;
}
struct Tree
{
#define ls x*2
#define rs x*2+1
ll s[N<<2];
void push_up(ll x)
{
s[x]=s[ls]+s[rs];
return;
}
void change(ll x,ll l,ll r,ll y,ll z)
{
if(l==r){
s[x]=max(s[x],y);
return;
}
ll mid=l+r>>1;
if(y<=r)change(ls,l,mid,y,z);
else change(rs,mid+1,r,y,z);
push_up(x);
return;
}
ll ask(ll x,ll L,ll R,ll l,ll r)
{
if(L==R)return s[x];
ll mid=L+R>>1;
if(mid<=r)return ask(ls,L,mid,l,r);
else if(mid>l)return ask(rs,mid+1,R,l,r);
else return ask(ls,L,mid,l,mid)+ask(rs,mid+1,R,mid+1,r);
}
}T;
void dfs(ll x)
{
sz[x]=1;
for(ll i=h[x];i;i=e[i].nx){
ll y=e[i].to;
if(y==fa[x])continue;
fa[y]=x;
dep[y]=dep[x]+1;
dfs(y);
sz[x]+=sz[y];
if(sz[y]>sz[hs[x]])hs[x]=y;
}
return;
}
void dfs1(ll x,ll anc)
{
dfn[x]=++w;
top[x]=anc;
if(hs[x])dfs1(hs[x],anc);
for(ll i=h[x];i;i=e[i].nx){
ll y=e[i].to;
if(y==fa[x]||y==hs[x])continue;
dfs1(y,y);
}
low[x]=++w;
return;
}
ll lca(ll x,ll y)
{
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return (dep[x]<dep[y]?x:y);
}
ll ask(ll x,ll y)
{
ll sum=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
if(hs[x])sum+=f[hs[x]];
sum+=T.ask(1,1,n,dfn[top[x]],dfn[x])-f[top[x]];
x=fa[top[x]];
}
if(top[x]>top[y])swap(x,y);
if(hs[y])sum+=f[hs[y]];
sum+=T.ask(1,1,n,dfn[x],dfn[y]);
return sum;
}
bool cmp(ll x,ll y)
{
return dep[x]>dep[y];
}
ll main()
{
scanf("%lld",&n);
for(ll i=1;i<n;++i){
scanf("%lld%lld",&x,&y);
addl(x,y);
addl(y,x);
}
fa[1]=1;
dep[1]=1;
dfs(1);
dfs1(1,1);
scanf("%lld",&m);
for(ll i=1;i<=m;++i){
scanf("%lld%lld%lld",&x,&y,&z);
ll u=lca(x,y);
d[u].push_back(mp(mp(x,y),z));
}
for(ll i=1;i<=n;++i)
v[i]=i;
sort(v+1,v+1+n,cmp);
for(ll i=1;i<=n;++i){
x=v[i];
f[x]=T.ask(1,1,n,dfn[x],dfn[x]);
if(hs[x])f[x]+=f[hs[x]];
for(ll j=0;j<d[x].size();++j){
f[x]=max(f[x],ask(d[x][j].fs.fs,d[x][j].fs.sn)+d[x][j].sn);
// printf("...........%d %d %d\n",d[x][j].fs.fs,d[x][j].fs.sn,ask(d[x][j].fs.fs,d[x][j].fs.sn));
}
ans=max(ans,f[x]);
// printf("%d %d\n",x,f[x]);
if(x!=1&&x==top[x])T.change(1,1,n,dfn[fa[x]],f[x]);
}
printf("%lld\n",ans);
return 0;
}
Compilation message (stderr)
election_campaign.cpp:7:1: error: 'll' does not name a type; did you mean 'ls'?
7 | ll n,m,ans,x,y,z,w,tot,h[N],f[N],sz[N],hs[N],top[N],fa[N],dep[N],dfn[N],low[N],v[N];
| ^~
| ls
election_campaign.cpp:8:18: error: 'll' was not declared in this scope; did you mean 'ls'?
8 | vector<pair<pair<ll,ll>,ll> >d[N];
| ^~
| ls
election_campaign.cpp:8:21: error: 'll' was not declared in this scope; did you mean 'ls'?
8 | vector<pair<pair<ll,ll>,ll> >d[N];
| ^~
| ls
election_campaign.cpp:8:23: error: template argument 1 is invalid
8 | vector<pair<pair<ll,ll>,ll> >d[N];
| ^
election_campaign.cpp:8:23: error: template argument 2 is invalid
election_campaign.cpp:8:25: error: 'll' was not declared in this scope; did you mean 'ls'?
8 | vector<pair<pair<ll,ll>,ll> >d[N];
| ^~
| ls
election_campaign.cpp:8:27: error: template argument 1 is invalid
8 | vector<pair<pair<ll,ll>,ll> >d[N];
| ^
election_campaign.cpp:8:27: error: template argument 2 is invalid
election_campaign.cpp:8:29: error: template argument 1 is invalid
8 | vector<pair<pair<ll,ll>,ll> >d[N];
| ^
election_campaign.cpp:8:29: error: template argument 2 is invalid
election_campaign.cpp:11:2: error: 'll' does not name a type; did you mean 'ls'?
11 | ll to,nx;
| ^~
| ls
election_campaign.cpp:13:6: error: variable or field 'addl' declared void
13 | void addl(ll x,ll y)
| ^~~~
election_campaign.cpp:13:11: error: 'll' was not declared in this scope; did you mean 'ls'?
13 | void addl(ll x,ll y)
| ^~
| ls
election_campaign.cpp:13:16: error: 'll' was not declared in this scope; did you mean 'ls'?
13 | void addl(ll x,ll y)
| ^~
| ls
election_campaign.cpp:24:2: error: 'll' does not name a type; did you mean 'ls'?
24 | ll s[N<<2];
| ^~
| ls
election_campaign.cpp:25:15: error: 'll' has not been declared
25 | void push_up(ll x)
| ^~
election_campaign.cpp:30:14: error: 'll' has not been declared
30 | void change(ll x,ll l,ll r,ll y,ll z)
| ^~
election_campaign.cpp:30:19: error: 'll' has not been declared
30 | void change(ll x,ll l,ll r,ll y,ll z)
| ^~
election_campaign.cpp:30:24: error: 'll' has not been declared
30 | void change(ll x,ll l,ll r,ll y,ll z)
| ^~
election_campaign.cpp:30:29: error: 'll' has not been declared
30 | void change(ll x,ll l,ll r,ll y,ll z)
| ^~
election_campaign.cpp:30:34: error: 'll' has not been declared
30 | void change(ll x,ll l,ll r,ll y,ll z)
| ^~
election_campaign.cpp:42:2: error: 'll' does not name a type; did you mean 'ls'?
42 | ll ask(ll x,ll L,ll R,ll l,ll r)
| ^~
| ls
election_campaign.cpp: In member function 'void Tree::push_up(int)':
election_campaign.cpp:27:3: error: 's' was not declared in this scope
27 | s[x]=s[ls]+s[rs];
| ^
election_campaign.cpp: In member function 'void Tree::change(int, int, int, int, int)':
election_campaign.cpp:33:4: error: 's' was not declared in this scope
33 | s[x]=max(s[x],y);
| ^
election_campaign.cpp:36:3: error: 'll' was not declared in this scope; did you mean 'l'?
36 | ll mid=l+r>>1;
| ^~
| l
election_campaign.cpp:37:23: error: 'mid' was not declared in this scope
37 | if(y<=r)change(ls,l,mid,y,z);
| ^~~
election_campaign.cpp:38:18: error: 'mid' was not declared in this scope
38 | else change(rs,mid+1,r,y,z);
| ^~~
election_campaign.cpp: At global scope:
election_campaign.cpp:51:6: error: variable or field 'dfs' declared void
51 | void dfs(ll x)
| ^~~
election_campaign.cpp:51:10: error: 'll' was not declared in this scope; did you mean 'ls'?
51 | void dfs(ll x)
| ^~
| ls
election_campaign.cpp:65:6: error: variable or field 'dfs1' declared void
65 | void dfs1(ll x,ll anc)
| ^~~~
election_campaign.cpp:65:11: error: 'll' was not declared in this scope; did you mean 'ls'?
65 | void dfs1(ll x,ll anc)
| ^~
| ls
election_campaign.cpp:65:16: error: 'll' was not declared in this scope; did you mean 'ls'?
65 | void dfs1(ll x,ll anc)
| ^~
| ls
election_campaign.cpp:78:1: error: 'll' does not name a type; did you mean 'ls'?
78 | ll lca(ll x,ll y)
| ^~
| ls
election_campaign.cpp:86:1: error: 'll' does not name a type; did you mean 'ls'?
86 | ll ask(ll x,ll y)
| ^~
| ls
election_campaign.cpp:100:10: error: 'll' was not declared in this scope; did you mean 'ls'?
100 | bool cmp(ll x,ll y)
| ^~
| ls
election_campaign.cpp:100:15: error: 'll' was not declared in this scope; did you mean 'ls'?
100 | bool cmp(ll x,ll y)
| ^~
| ls
election_campaign.cpp:100:19: error: expression list treated as compound expression in initializer [-fpermissive]
100 | bool cmp(ll x,ll y)
| ^
election_campaign.cpp:104:1: error: 'll' does not name a type; did you mean 'ls'?
104 | ll main()
| ^~
| ls