如何做网站上抓视频,网站自己的,搭建一个微信小程序要多少钱,搜索广告是什么https://www.nowcoder.com/acm/contest/172/C #xff08;sbw大佬太强啦 orz#xff09; 先把每一个路径(x,y)分成(x,lca),(y,lca)两个路径#xff0c;然后就能发现#xff0c;对于某两个#xff08;直上直下的#xff09;路径a,b#xff0c;b的下端点在a的下端点子树中… https://www.nowcoder.com/acm/contest/172/C sbw大佬太强啦 orz 先把每一个路径(x,y)分成(x,lca),(y,lca)两个路径然后就能发现对于某两个直上直下的路径a,bb的下端点在a的下端点子树中且b的上端点深度a的上端点深度那么b是覆盖a的。 这样的话我们做一个dfs序那么能覆盖某个路径的个数就是下端点在dfs序对应的那个区间中的、上端点深度小于要覆盖的那个路径的路径的个数。 而且比较容易发现我们要求的其实就是dfs序那个区间里的深度第k小的路径。 这样的话就可以搞一个主席树以深度为权值每条路径下端点的dfs序为时间往里加值每次只要询问对应区间的第k小就可以。 不过要注意的是我找出来的那个点深度大于我在做的这个点的深度的话是不合法的要判掉。 1 #includebits/stdc.h2 #define pa pairint,int3 #define ll long long4 using namespace std;5 const int maxn200020,logn22;6 7 ll rd(){8 ll x0;char cgetchar();int neg1;9 while(c0||c9){if(c-) neg-1;cgetchar();}10 while(c0c9) xx*10c-0,cgetchar();11 return x*neg;12 }13 14 int N,M,L,Q;15 int lg[maxn],dep[maxn],fa[maxn][logn];16 int egh[maxn],eg[maxn*2][2],ect;17 int pth[maxn],pt[maxn*2][2],pct;18 int id[maxn],dfn[maxn][2],tot,lst[maxn];19 int ch[maxn*logn*8][2],sum[maxn*logn*8],root[maxn*2],rct;20 21 inline void adeg(int a,int b){22 eg[ect][0]b;eg[ect][1]egh[a];egh[a]ect;23 }24 inline void adpt(int a,int d){25 pt[pct][0]d;pt[pct][1]pth[a];pth[a]pct;26 }27 28 void dfs(int x){29 dfn[x][0]tot;id[tot]x;30 for(int i1;fa[x][i-1]fa[fa[x][i-1]][i-1];i){31 fa[x][i]fa[fa[x][i-1]][i-1];32 }33 for(int iegh[x];i!-1;ieg[i][1]){34 if(dfn[eg[i][0]][0]) continue;35 dep[eg[i][0]]dep[x]1;fa[eg[i][0]][0]x;36 Lmax(L,dep[x]1);dfs(eg[i][0]);37 }dfn[x][1]tot;38 }39 40 inline int lca(int x,int y){41 if(dep[x]dep[y]) swap(x,y);42 while(dep[x]dep[y]){43 xfa[x][lg[dep[x]-dep[y]]];44 }if(xy) return x;45 for(int ilg[dep[x]-1];i0;i--){46 if(fa[x][i]!fa[y][i]) xfa[x][i],yfa[y][i];47 }return fa[x][0];48 }49 50 void add(int rn,int ro,int l,int r,int x){51 rnrct;sum[rn]sum[ro]1;52 if(lr){int mlr1;53 if(xm){54 add(ch[rn][0],ch[ro][0],l,m,x);ch[rn][1]ch[ro][1];55 }else{56 add(ch[rn][1],ch[ro][1],m1,r,x);ch[rn][0]ch[ro][0];57 }58 }59 }60 int query(int rn,int ro,int l,int r,int k){61 //printf(%d %d %d %d %d %d\n,l,r,rn,ro,sum[rn],sum[ro]);62 if(ksum[rn]-sum[ro]) return -1;63 if(lr) return l;64 else{65 int mlr1,wsum[ch[rn][0]]-sum[ch[ro][0]];66 if(wk) return query(ch[rn][0],ch[ro][0],l,m,k);67 else return query(ch[rn][1],ch[ro][1],m1,r,k-w);68 }69 }70 71 inline int solve(int x,int k){72 if(!k) return dep[x]-1;73 int yquery(root[lst[dfn[x][1]]],root[lst[dfn[x][0]-1]],1,L,k);74 if(y-1||dep[x]y) return 0;75 else return dep[x]-y;76 }77 78 int main(){79 //freopen(protect.in,r,stdin);80 int i,j,k;81 Nrd(),Mrd();memset(egh,-1,sizeof(egh));82 for(i1,j0,k2;iN10;i){83 if(ik) j,k1;lg[i]j;84 }85 for(i1;iN;i){86 int ard(),brd();87 adeg(a,b);adeg(b,a);88 }dep[1]1;dfs(1);memset(pth,-1,sizeof(pth));89 for(i1;iM;i){90 int ard(),brd();91 int xlca(a,b);92 adpt(a,dep[x]);adpt(b,dep[x]);93 }94 for(i1,k0;iN;i){95 for(jpth[id[i]];j!-1;jpt[j][1]){96 k;add(root[k],root[k-1],1,L,pt[j][0]);97 }lst[i]k;98 }99 Qrd();
100 for(i1;iQ;i){
101 int ard(),brd();
102 printf(%d\n,solve(a,b));
103 }
104 return 0;
105 } 转载于:https://www.cnblogs.com/Ressed/p/9628631.html
