COJ 1011 WZJ 의 데이터 구조 (11) 트 리 에 k 크기
12606 단어 데이터 구조
PS: 왜 내 가 처음에 N 발 을 Wa 했 는 지 는 왼쪽 구간 이 있어 서 내 가 [L, M + 1] 이 라 고 썼 기 때 문 이 야..............................................
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<algorithm>
5 #include<queue>
6 #include<cstring>
7 #define PAU putchar(' ')
8 #define ENT putchar('
')
9 using namespace std;
10 const int maxn=100000+10,maxnode=20000000+10,maxn2=200000+10;
11 int ls[maxnode],rs[maxnode],s[maxnode],A[maxn],root[maxn],p[maxn],si[maxn],so[maxn],siz[maxn],cz=0,tot=0;
12 struct tedge{int x,y,next;}adj[maxn2];int ms=0,fch[maxn];
13 void addedge(int u,int v){
14 adj[++ms]=(tedge){u,v,fch[u]};fch[u]=ms;
15 adj[++ms]=(tedge){v,u,fch[v]};fch[v]=ms;
16 return;
17 }
18 void build(int x,int&y,int L,int R,int pos){
19 s[y=++tot]=s[x]+1;if(L==R) return;
20 int M=L+R>>1;21 if(pos<=M) rs[y]=rs[x],build(ls[x],ls[y],L,M,pos);
22 else ls[y]=ls[x],build(rs[x],rs[y],M+1,R,pos);
23 }
24 int query(int x,int y,int L,int R,int k){
25 if(L==R) return L;int M=L+R>>1,kth=s[ls[y]]-s[ls[x]];
26 if(k<=kth) return query(ls[x],ls[y],L,M,k);
27 else return query(rs[x],rs[y],M+1,R,k-kth);
28 }
29 void dfs(int u,int fa){
30 si[u]=++cz;p[cz]=u;siz[u]=1;
31 for(int i=fch[u];i;i=adj[i].next){
32 int v=adj[i].y;
33 if(v!=fa) dfs(v,u),siz[u]+=siz[v];
34 } so[u]=cz;return;
35 }
36 inline int read(){
37 int x=0,sig=1;char ch=getchar();
38 while(!isdigit(ch)){if(ch=='-')sig=-1;ch=getchar();}
39 while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
40 return x*=sig;
41 }
42 inline void write(int x){
43 if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;
44 int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;
45 for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;
46 }
47 int n,Q;
48 void init(){
49 n=read();Q=read();
50 for(int i=1;i<n;i++) addedge(read(),read());
51 for(int i=1;i<=n;i++) A[i]=read();
52 dfs(1,0);
53 for(int i=1;i<=n;i++) build(root[i-1],root[i],1,n,A[p[i]]);
54 return;
55 }
56 void work(){
57 int x,k;
58 while(Q--){
59 x=read();k=read();
60 if(siz[x]<k) puts("-1");
61 else write(query(root[si[x]-1],root[so[x]],1,n,k)),ENT;
62 }
63 return;
64 }
65 void print(){
66 return;
67 }
68 int main(){init();work();print();return 0;}
수색 하 다.
복제 하 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.