首页 > 代码库 > JZOJ5257.【NOIP2017模拟8.11】小X的佛光
JZOJ5257.【NOIP2017模拟8.11】小X的佛光
题目就是要求两点到一个点的路径中重叠的点的个数。
特殊性质一是一条链，我们可以通过讨论两个起点和一个终点的相对位置直接得出答案。
特殊性质二的两个起点相同，就是要我们求树上两点之间的点的个数，求出两点LCA，预处理点到根节点的距离，再根据LCA是不是根节点决定距离相减或相加就可以了。
考虑100分的，仍然要LCA，然后分类讨论就可以了......
我们记num[i]为i到根节点的点的个数（包括根节点和它自己）
第一种是LCAab和LCAcb相等，那么我们求LCAac,答案就是num[LCAac]+num[B]-num[LCAab]+1。（这里的一个点到根节点的个数包括根节点和它本身。）
第二种是LCAab和LCAcb不相等，如果LCAab和LCAcb中有一个是B的，那么答案就是1，如果都不是B，那么我们再求LCALCAab LCAcb，这个时候它们的LCA必是其中的一个（可用反证法证明），如果是LCAab，那么答案就是num[B]-num[LCAcb]+1，否则就是LCAcb，答案为num[B]-num[LCAab]+1。
LCA用树上倍增或者欧拉迹+ST就可以啦（欧拉迹数组似乎要开很大QAQRE好久）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #define N 600001 8 using namespace std; 9 int n,m,p,t,ans,head[N*2],next[N*2],to[N*2],visit[N],deep[N*2],ji[N*2],num,ti,ge[N],f[N][100],qwq[N][100];10 void add(int u,int v){11 num++;12 next[num]=head[u];13 to[num]=v;14 head[u]=num;15 num++;16 next[num]=head[v];17 to[num]=u;18 head[v]=num;19 }20 void dfs(int x,int nu,int d){21 if (!visit[x]) visit[x]=++ti;22 ji[ti]=x;23 deep[ti]=d;24 ge[x]=nu;25 for (int i=head[x],v;i!=0;i=next[i]){26 v=to[i];27 if (!visit[v]) {28 dfs(v,nu+1,d+1);29 ji[++ti]=x;30 deep[ti]=d; 31 }32 }33 }34 void ST(){35 int tmp=(int)(log(ti)/log(2));36 for (int i=1;i<=ti;i++){37 f[i][0]=deep[i];38 qwq[i][0]=ji[i];39 }40 for (int j=1;j<=tmp;j++)41 for (int i=1;i<=ti;i++){42 int k=1<<(j-1);43 if (i-k<=ti)44 if (f[i][j-1]<f[i+k][j-1]){45 f[i][j]=f[i][j-1];46 qwq[i][j]=qwq[i][j-1];47 }48 else{49 f[i][j]=f[i+k][j-1];50 qwq[i][j]=qwq[i+k][j-1];51 }52 }53 }54 int lca(int x,int y){55 int a=min(visit[x],visit[y]);56 int b=max(visit[y],visit[x]);57 int tmp=(int)(log((b-a)+1)/log(2));58 if (f[a][tmp]<f[b-(1<<(tmp))+1][tmp])59 return qwq[a][tmp];60 else return qwq[b-(1<<(tmp))+1][tmp];61 }62 void work(int a,int b,int c){63 int d=0,e=0;64 d=lca(a,b);65 e=lca(b,c);66 if (d==e){67 int x=lca(a,c);68 printf("%d\n",ge[x]+ge[b]-2*ge[d]+1);69 }70 else if ((d==b)||(e==b)) printf("1\n");71 else {72 int x=lca(d,e);73 if (x==d) printf("%d\n",ge[b]-ge[e]+1);74 else if (x==e) printf("%d\n",ge[b]-ge[d]+1);75 }76 }77 int main(){ 78 scanf("%d%d%d",&n,&m,&p);79 for (int i=1,u,v;i<n;i++){80 scanf("%d%d",&u,&v);81 add(u,v);82 }83 dfs(1,1,0);84 ST();85 for (int i=1,u,v,w;i<=m;i++){86 scanf("%d%d%d",&u,&v,&w);87 work(u,v,w);88 }89 return 0;90 }
（似乎JZ评测集下会爆栈...根节点设为n/2也可以）（明明20万数据莫名60万才过了QAQ）
还有一个水水的程序（输入数据还好良心，告诉你性质）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #define N 500001 8 using namespace std; 9 int n,m,p,t,ans,head[N*2],next[N*2],to[N*2],visit[N],deep[N*2],ji[N*2],num,ti,ge[N],f[N][100],qwq[N][100]; 10 void add(int u,int v){ 11 num++; 12 next[num]=head[u]; 13 to[num]=v; 14 head[u]=num; 15 num++; 16 next[num]=head[v]; 17 to[num]=u; 18 head[v]=num; 19 } 20 void shui1(){ 21 for (int i=1,u,v,w;i<=m;i++){ 22 scanf("%d%d%d",&u,&v,&w); 23 if ((v>=u)&&(v>=w)) printf("%d\n",v-max(u,w)+1); 24 else if (((v>=u)&&(v<=w))||(v<=u)&&v>=w) printf("1\n"); 25 else if ((v<=u)&&(v<=w)) printf("%d\n",min(u,w)-v+1); 26 } 27 } 28 void dfs(int x,int nu,int d){ 29 if (!visit[x]) visit[x]=++ti; 30 ji[ti]=x; 31 deep[ti]=d; 32 ge[x]=nu; 33 for (int i=head[x],v;i!=0;i=next[i]){ 34 v=to[i]; 35 if (!visit[v]) { 36 dfs(v,nu+1,d+1); 37 ji[++ti]=x; 38 deep[ti]=d; 39 } 40 } 41 } 42 void ST(){ 43 int tmp=(int)(log(ti)/log(2)); 44 for (int i=1;i<=ti;i++){ 45 f[i][0]=deep[i]; 46 qwq[i][0]=ji[i]; 47 } 48 for (int j=1;j<=tmp;j++) 49 for (int i=1;i<=ti;i++){ 50 int k=1<<(j-1); 51 if (i-k<=ti) 52 if (f[i][j-1]<f[i+k][j-1]){ 53 f[i][j]=f[i][j-1]; 54 qwq[i][j]=qwq[i][j-1]; 55 } 56 else{ 57 f[i][j]=f[i+k][j-1]; 58 qwq[i][j]=qwq[i+k][j-1]; 59 } 60 } 61 } 62 int lca(int x,int y){ 63 int a=min(visit[x],visit[y]); 64 int b=max(visit[y],visit[x]); 65 int tmp=(int)(log((b-a)+1)/log(2)); 66 if (f[a][tmp]<f[b-(1<<(tmp))+1][tmp]) 67 return qwq[a][tmp]; 68 else return qwq[b-(1<<(tmp))+1][tmp]; 69 } 70 void shui2(){ 71 for (int i=1,u,v,w,x;i<=m;i++){ 72 scanf("%d%d%d",&u,&v,&w); 73 x=lca(u,v); 74 if (x==1) printf("%d\n",ge[u]+ge[v]-1); 75 else printf("%d\n",ge[u]+ge[v]-2*ge[x]+1); 76 } 77 } 78 void work(int a,int b,int c){ 79 int d=0,e=0; 80 d=lca(a,b); 81 e=lca(b,c); 82 if (d==e){ 83 int x=lca(a,c); 84 printf("%d\n",ge[x]+ge[b]-2*ge[d]+1); 85 } 86 else if ((d==b)||(e==b)) printf("1\n"); 87 else { 88 int x=lca(d,e); 89 if (x==d) printf("%d\n",ge[b]-ge[e]+1); 90 else if (x==e) printf("%d\n",ge[b]-ge[d]+1); 91 } 92 } 93 int main(){ 94 scanf("%d%d%d",&n,&m,&p); 95 for (int i=1,u,v;i<n;i++){ 96 scanf("%d%d",&u,&v); 97 add(u,v); 98 } 99 if ((p==11)||(p==12)||(p==13)||(p==17)||(p==18)){100 shui1(); return 0;101 }102 ti=0;103 dfs(1,1,0);104 ST();105 if ((p==14)||(p==15)||(p==19)){106 shui2(); return 0;107 }108 for (int i=1,u,v,w;i<=m;i++){109 scanf("%d%d%d",&u,&v,&w);110 work(u,v,w);111 }112 return 0;113 }
JZOJ5257.【NOIP2017模拟8.11】小X的佛光
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。