题意概述:
给出一棵 N 个结点的树, 然后有 M 个居民分散在这棵树的结点上 (允许某个结点没有居民) 现在给出一些询问形如 u,v,a, 定义 k=min(x,a), 其中 x 表示的是 u->v 路径上的居民数量将所有路径上的居民编号升序排列之后得到序列 p1,p2,...,px, 要求对于每一组询问, 输出 k,p1,p2,...,pk
N,M,Q<=10^5,1<=a<=10.
分析:
实际上这个题是被丢在数据结构作业里面的只是好像没有这个必要?
分析一波可以发现每个点可能在答案中出现的居民最多只有 10 个, 所以说按照出现的顺序依次把每个点的至多 10 个居民储存起来, 然后倍增的时候用归并排序的思想合并就可以了时间复杂度 O(10nlogn)
实现过程中注意到一些问题, 今后用倍增统计点的信息的时候都用半开半闭就好了, 加上对链顶端 (x=y 时对 x, 否则 x,y 一起爬之后对 x,y,fa[x][0]) 的特判就可以做到不重不漏统计(之前都是用来求最值之类的所以没有注意到这个问题)
然后还有为什么倍增数组第二维开成 17 省省空间在 100000 的时候 wa 了有哪位 dalao 可以告诉我
所以数据结构是树的意思吗(感觉听了小火车讲课之后写代码的时候都在各种压长度?)
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<cstdlib>
- #include<algorithm>
- #include<cmath>
- #include<queue>
- #include<set>
- #include<map>
- #include<vector>
- #include<cctype>
- using namespace std;
- const int maxn=100005;
- int N,M,Q;
- struct edge{ int to,next; }E[maxn<<1];
- int first[maxn],np,dep[maxn],fa[maxn][18],info[maxn][18][11],sz[maxn][18];
- int ans[25],tmp[25];
- void add_edge(int u,int v)
- {
- E[++np]=(edge){v,first[u]};
- first[u]=np;
- }
- void data_in()
- {
- scanf("%d%d%d",&N,&M,&Q);
- int x,y;
- for(int i=1;i<N;i++){
- scanf("%d%d",&x,&y);
- add_edge(x,y);
- add_edge(y,x);
- }
- for(int i=1;i<=M;i++){
- scanf("%d",&x);
- if(sz[x][0]<10) info[x][0][sz[x][0]++]=i;
- }
- }
- int merge(int *a,int *b,int l1,int l2,int *c)
- {
- int l=0,i=0,j=0;
- while(i<l1&&j<l2) c[l++]=a[i]<b[j]?a[i++]:b[j++];
- while(i<l1) c[l++]=a[i++];
- while(j<l2) c[l++]=b[j++];
- return min(l,10);
- }
- void DFS(int i,int f,int d)
- {
- fa[i][0]=f,dep[i]=d;
- for(int j=1;(1<<j)<d;j++){
- fa[i][j]=fa[fa[i][j-1]][j-1];
- sz[i][j]=merge(info[i][j-1],info[fa[i][j-1]][j-1],sz[i][j-1],sz[fa[i][j-1]][j-1],info[i][j]);
- }
- for(int p=first[i];p;p=E[p].next){
- int j=E[p].to;
- if(j==f) continue;
- DFS(j,i,d+1);
- }
- }
- void cc(int *n,int &l,int x,int i)
- {
- l=merge(n,info[x][i],l,sz[x][i],tmp);
- for(int k=0;k<l;k++) n[k]=tmp[k];
- }
- void LCA(int x,int y,int *n,int &l)
- {
- if(dep[x]<dep[y]) swap(x,y);
- int len=dep[x]-dep[y]; l=0;
- for(int i=0;(1<<i)<=len;i++)
- if((1<<i)&len){ cc(n,l,x,i); x=fa[x][i]; }
- if(x==y){ cc(n,l,x,0); return; }
- for(int i=16;i>=0;i--) if(fa[x][i]!=fa[y][i]){
- cc(n,l,x,i); cc(n,l,y,i);
- x=fa[x][i],y=fa[y][i];
- }
- cc(n,l,x,0); cc(n,l,y,0);
- cc(n,l,fa[x][0],0);
- }
- void work()
- {
- DFS(1,0,1);
- int x,y,z,a,l;
- for(int i=1;i<=Q;i++){
- scanf("%d%d%d",&x,&y,&a);
- LCA(x,y,ans,l);
- printf("%d",min(a,l));
- for(int j=0;j<min(a,l);j++) printf("%d",ans[j]);
- printf("\n");
- }
- }
- int main()
- {
- freopen("test.in","r",stdin);
- freopen("test.out","w",stdout);
- data_in();
- work();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2503301.html