#include <bits/stdc++.h>
#define MAXN 100007
#define MAXL 18
using namespace std;
vector<int> g[MAXN],vl,br,vr;
int in[MAXN],out[MAXN],p[MAXL][MAXN],t,n,c[MAXN],rd[MAXN],d[MAXN],seg[4*MAXN];
long long bit[MAXN];
map<int,int> mp;
void updseg(int l,int r,int x,int v,int ind)
{
if(l==r) {seg[ind]=v; return;}
int s=(l+r)/2;
if(x<=s) updseg(l,s,x,v,2*ind);
else updseg(s+1,r,x,v,2*ind+1);
seg[ind]=max(seg[2*ind],seg[2*ind+1]);
}
int val(int l,int r,int lt,int rt,int ind)
{
if(l>=lt && r<=rt) return seg[ind];
if(r<lt || l>rt) return 0;
int s=(l+r)/2;
return max(val(l,s,lt,rt,2*ind),val(s+1,r,lt,rt,2*ind+1));
}
void dfs(int s,int dub)
{
in[s]=++t;
d[s]=dub;
for(int i=0;i<g[s].size();i++) dfs(g[s][i],dub+1);
out[s]=t;
}
void lcainit()
{
dfs(1,0); p[0][1]=1;
for(int i=1;i<MAXL;i++) for(int j=1;j<=n;j++) p[i][j]=p[i-1][p[i-1][j]];
}
bool insub(int u,int v) {return in[u]<=in[v] && out[u]>=out[v];}
int lca(int u,int v)
{
for(int i=MAXL-1;i>=0;i--) if(!insub(p[i][u],v)) u=p[i][u];
return u;
}
void upd(int x,int val)
{
while(x<MAXN)
{
bit[x]+=val;
x+=x&-x;
}
}
long long fnd(int x)
{
long long sm=0;
while(x)
{
sm+=bit[x];
x-=x&-x;
}
return sm;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) {scanf("%d",&c[i]); vl.push_back(c[i]);}
sort(vl.begin(),vl.end());
for(int i=0;i<n;i++) mp[vl[i]]=n-i;
for(int i=0;i<n;i++) c[i]=mp[c[i]];
for(int i=1;i<n;i++)
{
int t1,t2;
scanf("%d%d",&t1,&t2);
g[t1].push_back(t2);
p[0][t2]=t1;
rd[i]=t2;
}
lcainit();
rd[0]=1;
for(int i=1;i<n;i++)
{
int x=1; long long sol=0;
while(x!=rd[i])
{
int r=val(1,n,in[x],out[x],1);
int w=lca(rd[i],rd[r]);
br.push_back(c[rd[r]]); vr.push_back(d[x]-d[w]);
/*sol+=((long long)d[w]-d[x])*fnd(c[rd[r]]-1);*/
upd(c[rd[r]],d[w]-d[x]);
x=w;
}
updseg(1,n,in[rd[i]],i,1);
for(int j=0;j<br.size();j++) upd(br[j],vr[j]);
br.clear(); vr.clear();
printf("%lld\n",sol);
}
}
Compilation message
construction.cpp: In function 'void dfs(int, int)':
construction.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) dfs(g[s][i],dub+1);
~^~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:90:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<br.size();j++) upd(br[j],vr[j]);
~^~~~~~~~~~
construction.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
construction.cpp:63:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++) {scanf("%d",&c[i]); vl.push_back(c[i]);}
~~~~~^~~~~~~~~~~~
construction.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&t1,&t2);
~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
