| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 917032 | firewater | Election Campaign (JOI15_election_campaign) | C++14 | 0 ms | 0 KiB |
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
#define ll long long
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;
}