#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define L (idx*2)
#define R (idx*2)+1
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
int n,a,b,k,t[200005],ss,arr[200005],ans,l[200005],r[200005],nn[200005],lz[800005],seq[800005],seq1[800005],lz1[800005],c,kk;
vector<int>v[200005];
void gen(int N,int pr,int cc)
{
arr[cc]=t[N];
for(int i=0;i<v[N].size();i++)
{
if(v[N][i]!=pr)
{
gen(v[N][i],N,cc+1);
}
}
return;
}
void up_seq(int st,int ed,int idx,int ll,int rr,int val)
{
int mid=(st+ed)/2;
if(lz[idx]!=0)
{
seq[idx]+=lz[idx];
if(st!=ed)
{
lz[L]+=lz[idx];
lz[R]+=lz[idx];
}
lz[idx]=0;
}
if(st>rr||ed<ll)return;
if(ll<=st&&rr>=ed)
{
seq[idx]+=val;
if(st!=ed)
{
lz[L]+=val;
lz[R]+=val;
}
return;
}
up_seq(st,mid,L,ll,rr,val);
up_seq(mid+1,ed,R,ll,rr,val);
seq[idx]=max(seq[L],seq[R]);
}
int mx_seq(int st,int ed,int idx,int ll,int rr)
{
int mid=(st+ed)/2;
if(lz[idx]!=0)
{
seq[idx]+=lz[idx];
if(st!=ed)
{
lz[L]+=lz[idx];
lz[R]+=lz[idx];
}
lz[idx]=0;
}
if(st>rr||ed<ll)return -1;
if(ll<=st&&rr>=ed)return seq[idx];
return max(mx_seq(st,mid,L,ll,rr),mx_seq(mid+1,ed,R,ll,rr));
}
void up_seq1(int st,int ed,int idx,int ll,int rr,int val)
{
int mid=(st+ed)/2;
if(lz1[idx]!=0)
{
seq1[idx]+=lz1[idx];
if(st!=ed)
{
lz1[L]+=lz1[idx];
lz1[R]+=lz1[idx];
}
lz1[idx]=0;
}
if(st>rr||ed<ll)return;
if(ll<=st&&rr>=ed)
{
seq1[idx]+=val;
if(st!=ed)
{
lz1[L]+=val;
lz1[R]+=val;
}
return;
}
up_seq1(st,mid,L,ll,rr,val);
up_seq1(mid+1,ed,R,ll,rr,val);
seq[idx]=max(seq[L],seq[R]);
}
int mx_seq1(int st,int ed,int idx,int ll,int rr)
{
int mid=(st+ed)/2;
if(lz1[idx]!=0)
{
seq1[idx]+=lz1[idx];
if(st!=ed)
{
lz1[L]+=lz1[idx];
lz1[R]+=lz1[idx];
}
lz1[idx]=0;
}
if(st>rr||ed<ll)return -1;
if(ll<=st&&rr>=ed)return seq1[idx];
return max(mx_seq1(st,mid,L,ll,rr),mx_seq1(mid+1,ed,R,ll,rr));
}
int main()
{
scanf("%d %d",&n,&k);
ans=k-1;
for(int i=1;i<n;i++)
{
scanf("%d %d",&a,&b);
v[a].pb(b);
v[b].pb(a);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&t[i]);
if(v[i].size()==1)ss=i;
}
gen(ss,0,1);
for(int i=1;i<=n;i++)
{
nn[arr[i]]++;
if(nn[arr[i]]==1)
{
l[arr[i]]=i;
}
r[arr[i]]=i;
}
for(int i=1;i<=n;i++)
{
up_seq(1,n,1,i,i,i-1);
}
for(int i=1;i<=n;i++)
{
if(r[arr[i]]==i)
{
//printf("==%d %d\n",l[arr[i]],nn[arr[i]]);
up_seq(1,n,1,1,l[arr[i]],nn[arr[i]]);
up_seq1(1,n,1,1,l[arr[i]],1);
}
else continue;
a=1,b=i,kk=0;
//printf("%d\n",mx_seq(1,n,1,1,i));
if(mx_seq(1,n,1,1,i)!=i)continue;
while(a<=b)
{
c=(a+b)/2;
if(mx_seq(1,n,1,c,i)==i)
{
kk=max(kk,c);
a=c+1;
}
else
{
b=c-1;
}
}
ans=min(ans,mx_seq1(1,n,1,kk,kk)-1);
}
printf("%d",ans);
}
Compilation message
capital_city.cpp: In function 'void gen(int, int, int)':
capital_city.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0;i<v[N].size();i++)
| ~^~~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
123 | scanf("%d %d",&n,&k);
| ~~~~~^~~~~~~~~~~~~~~
capital_city.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
127 | scanf("%d %d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~~
capital_city.cpp:133:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
133 | scanf("%d",&t[i]);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1018 ms |
32448 KB |
Output is correct |
| 2 |
Correct |
966 ms |
32384 KB |
Output is correct |
| 3 |
Correct |
1054 ms |
32304 KB |
Output is correct |
| 4 |
Correct |
1012 ms |
32336 KB |
Output is correct |
| 5 |
Correct |
991 ms |
32252 KB |
Output is correct |
| 6 |
Correct |
966 ms |
32296 KB |
Output is correct |
| 7 |
Correct |
935 ms |
31948 KB |
Output is correct |
| 8 |
Correct |
820 ms |
31560 KB |
Output is correct |
| 9 |
Correct |
272 ms |
34796 KB |
Output is correct |
| 10 |
Correct |
258 ms |
34732 KB |
Output is correct |
| 11 |
Correct |
268 ms |
34796 KB |
Output is correct |
| 12 |
Correct |
276 ms |
34796 KB |
Output is correct |
| 13 |
Correct |
250 ms |
34796 KB |
Output is correct |
| 14 |
Correct |
252 ms |
34668 KB |
Output is correct |
| 15 |
Correct |
277 ms |
34720 KB |
Output is correct |
| 16 |
Correct |
255 ms |
34788 KB |
Output is correct |
| 17 |
Correct |
278 ms |
34792 KB |
Output is correct |
| 18 |
Correct |
267 ms |
34668 KB |
Output is correct |
| 19 |
Correct |
252 ms |
34796 KB |
Output is correct |
| 20 |
Correct |
259 ms |
34668 KB |
Output is correct |
| 21 |
Correct |
4 ms |
5100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
