你的f[k][0]=k是什么操作？？？
by 913887524gsd @ 2018-11-09 07:07:49
@[913887524gsd](/space/show?uid=89367) 额，代码好像发错了，这是改到一半的代码，抱歉。
```cpp
#include<cstdio>
using namespace std;
int n,m,s,fa[500007][27],d[500007],lg[500007],p[1000007],v[1000007],h[500007],l,x,y,z;
int f(int k,int w)
{
for (int i=h[k];i;i=p[i])
{
int u=v[i];
if (!d[u])
{
d[u]=w+1;
fa[u][0]=k;
for (int j=1;j<w;++j)
fa[u][j]=fa[fa[u][j-1]][j-1];
f(u,w+1);
}
}
}
int f1(int vx,int vy)
{
if (d[vx]<d[vy])
{
int num=vx;
vx=vy;
vy=num;
}
for (int i=lg[vx];i>=0;--i)
if(d[fa[vx][i]]>=d[vy])
vx=fa[vx][i];
if (vx==vy)
return vx;
for (int i=lg[vx];i>=0;--i)
if (fa[vx][i]!=fa[vy][i])
{
vx=fa[vx][i];
vy=fa[vy][i];
}
return fa[vx][0];
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for (int i=2;i<=n;++i)
lg[i]=lg[i>>1]+1;
for (int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
v[++l]=x;
p[l]=h[y];
h[y]=l;
v[++l]=y;
p[l]=h[x];
h[x]=l;
}
d[s]=1;
f(s,1);
for (int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
printf("%d\n",f1(x,y));
}
return 0;
}
```
by 奔跑吧柯哀 @ 2018-11-09 07:09:53
f[k][0]=k;
23333
by 用户已注销 @ 2018-11-09 07:10:25
@[913887524gsd](/space/show?uid=89367)
20分代码
```cpp
#include<cstdio>
using namespace std;
int n,m,s,fa[500007][27],d[500007],lg[500007],p[1000007],v[1000007],h[500007],l,x,y,z;
int f(int k,int w)
{
for (int i=h[k];i;i=p[i])
{
int u=v[i];
if (!d[u])
{
d[u]=w+1;
fa[u][0]=k;
for (int j=1;j<w;++j)
fa[u][j]=fa[fa[u][j-1]][j-1];
f(u,w+1);
}
}
}
int f1(int vx,int vy)
{
if (d[vx]<d[vy])
{
int num=vx;
vx=vy;
vy=num;
}
for (int i=lg[vx];i>=0;--i)
if(d[fa[vx][i]]>=d[vy])
vx=fa[vx][i];
if (vx==vy)
return vx;
for (int i=lg[vx];i>=0;--i)
if (fa[vx][i]!=fa[vy][i])
{
vx=fa[vx][i];
vy=fa[vy][i];
}
return fa[vx][0];
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for (int i=2;i<=n;++i)
lg[i]=lg[i>>1]+1;
for (int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
v[++l]=x;
p[l]=h[y];
h[y]=l;
v[++l]=y;
p[l]=h[x];
h[x]=l;
}
d[s]=1;
f(s,1);
for (int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
printf("%d\n",f1(x,y));
}
return 0;
}
```
by 奔跑吧柯哀 @ 2018-11-09 07:11:12
@[fzszkl](/space/show?uid=23323) 抱歉，发错了，那是改到一半的代码。
by 奔跑吧柯哀 @ 2018-11-09 07:11:44
你的求lca那里有问题，应该为```
for(int i=lg[d[dx]];i>=0;i--)
```
by 913887524gsd @ 2018-11-09 07:21:24
找到一个小错。。。
```
for (int i=lg[vx];i>=0;--i)
if(d[fa[vx][i]]>=d[vy])
vx=fa[vx][i];
if (vx==vy)
return vx;
for (int i=lg[vx];i>=0;--i)
if (fa[vx][i]!=fa[vy][i])
{
vx=fa[vx][i];
vy=fa[vy][i];
}
```
lg[vx]...把编号log一下好像没啥意义吧
我不会写倍增LCA啊丢人了，建议学树链剖分LCA，代码短跑的还快
by 用户已注销 @ 2018-11-09 07:21:52
嗯。。。我试着交了一下你的代码，AC了。
```
#include<cstdio>
using namespace std;
int n,m,s,fa[500007][27],d[500007],lg[500007],p[1000007],v[1000007],h[500007],l,x,y,z;
int f(int k,int w)
{
for (int i=h[k];i;i=p[i])
{
int u=v[i];
if (!d[u])
{
d[u]=w+1;
fa[u][0]=k;
for (int j=1;j<=lg[w];++j)
fa[u][j]=fa[fa[u][j-1]][j-1];
f(u,w+1);
}
}
}
int f1(int vx,int vy)
{//printf("a\n");
if (d[vx]<d[vy])
{
int num=vx;
vx=vy;
vy=num;
}//printf("b\n");
for (int i=lg[d[vx]]+1;i>=0;--i)
if(d[fa[vx][i]]>=d[vy])
vx=fa[vx][i];
if (vx==vy)
return vx;//printf("c\n");
for (int i=lg[d[vx]]+1;i>=0;--i)
if (fa[vx][i]!=fa[vy][i])
{
vx=fa[vx][i];
vy=fa[vy][i];
}//printf("d\n");
return fa[vx][0];
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for (int i=2;i<=n;++i)
lg[i]=lg[i>>1]+1;
for (int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
v[++l]=x;
p[l]=h[y];
h[y]=l;
v[++l]=y;
p[l]=h[x];
h[x]=l;
}
d[s]=1;
f(s,1);
for (int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
printf("%d\n",f1(x,y));
}
return 0;
}
```
一番魔改，希望你不要介意
其实就是倍增的时候改成了log+1就A了。。。
by 用户已注销 @ 2018-11-09 07:27:30
树剖
评测状态
Accepted 100
用时: 659ms / 内存: 21524KB
by 用户已注销 @ 2018-11-09 07:32:44
@[fzszkl](/space/show?uid=23323) 恩，我改成lg+1了，多了十分
[评测记录](https://www.luogu.org/record/show?rid=13521726)
```cpp
#include<cstdio>
using namespace std;
int n,m,s,fa[500007][27],d[500007],lg[500007],p[1000007],v[1000007],h[500007],l,x,y,z;
int f(int k,int w)
{
for (int i=h[k];i;i=p[i])
{
int u=v[i];
if (!d[u])
{
d[u]=w+1;
fa[u][0]=k;
for (int j=1;j<w;++j)
fa[u][j]=fa[fa[u][j-1]][j-1];
f(u,w+1);
}
}
return 0;
}
int f1(int vx,int vy)
{
if (d[vx]<d[vy])
{
int num=vx;
vx=vy;
vy=num;
}
for (int i=lg[d[vx]]+1;i>=0;--i)
if(d[fa[vx][i]]>=d[vy])
vx=fa[vx][i];
if (vx==vy)
return vx;
for (int i=lg[d[vx]]+1;i>=0;--i)
if (fa[vx][i]!=fa[vy][i])
{
vx=fa[vx][i];
vy=fa[vy][i];
}
return fa[vx][0];
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for (int i=2;i<=n;++i)
lg[i]=lg[i>>1]+1;
for (int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
v[++l]=x;
p[l]=h[y];
h[y]=l;
v[++l]=y;
p[l]=h[x];
h[x]=l;
}
d[s]=1;
f(s,1);
for (int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
printf("%d\n",f1(x,y));
}
return 0;
}
```
by 奔跑吧柯哀 @ 2018-11-09 07:37:50