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 <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
struct qr
{
int n1,n2,cost;
};
vector<qr> L[nmax];
vector<int> v[nmax];
int tt[20][nmax];
int l[nmax],r[nmax],aib[nmax],dp[nmax],sons[nmax];
int n,m,i,j,nr,a,b,c,al,bl,t;
inline int lbit(int x)
{
return ((x^(x-1))&x);
}
void update(int poz,int val)
{
for(int idx=poz;idx<=n;idx+=lbit(idx))
aib[idx]+=val;
}
int compute(int poz)
{
int ret=0;
for(int idx=poz;idx>0;idx-=lbit(idx))
ret+=aib[idx];
return ret;
}
void dfs(int x)
{
l[x]=++nr;
for(int i=0;i<v[x].size();i++)
if(!l[v[x][i]])
{
tt[0][v[x][i]]=x;
dfs(v[x][i]);
}
r[x]=nr;
}
void chef()
{
for(int i=1;i<=16;i++)
for(int j=1;j<=n;j++)
tt[i][j]=tt[i-1][tt[i-1][j]];
}
bool cup(int a,int b)
{
return (l[a]<=l[b]&&l[b]<=r[a]);
}
int lca(int a,int b)
{
int stram=0;
for(int p=16;p>=0;p--)
{
stram=tt[p][a];
if(stram&&(!cup(stram,b)))
a=stram;
}
if(!cup(a,b))
a=tt[0][a];
return a;
}
int nxt(int a,int L)
{
if(a==L) return 0;
for(int p=16;p>=0;p--)
if(tt[p][a]&&(!cup(tt[p][a],L)))
a=tt[p][a];
return a;
}
void defeseu(int x)
{
for(int i=0;i<v[x].size();i++)
if(l[v[x][i]]>l[x])
defeseu(v[x][i]);
int sum=0;
for(int i=0;i<v[x].size();i++)
sum+=dp[v[x][i]];
dp[x]=sum;sons[x]=sum;
for(int i=0;i<L[x].size();i++)
{
a=L[x][i].n1;b=L[x][i].n2;c=L[x][i].cost;
al=nxt(a,x);bl=nxt(b,x);
if(sum-dp[al]-dp[bl]+compute(l[a])+compute(l[b])+c+sons[a]*(a!=x)+sons[b]*(b!=x)>dp[x])
dp[x]=sum-dp[al]-dp[bl]+compute(l[a])+compute(l[b])+c+sons[a]*(a!=x)+sons[b]*(b!=x);
}
int nod;
for(int i=0;i<v[x].size();i++)
if(l[v[x][i]]>l[x])
{
nod=v[x][i];
sum-=dp[nod];
update(l[nod],sum);
update(r[nod]+1,-sum);
sum+=dp[nod];
}
}
int main()
{
// freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n;
for(i=1;i<=n-1;i++)
{
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1);
chef();
cin>>m;
for(i=1;i<=m;i++)
{
cin>>a>>b>>c;
t=lca(a,b);
L[t].push_back({a,b,c});
}
defeseu(1);
cout<<dp[1];
return 0;
}
Compilation message (stderr)
election_campaign.cpp: In function 'void dfs(int)':
election_campaign.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
election_campaign.cpp: In function 'void defeseu(int)':
election_campaign.cpp:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
election_campaign.cpp:79:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
election_campaign.cpp:82:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<L[x].size();i++)
~^~~~~~~~~~~~
election_campaign.cpp:90:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
# | 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... |