~~红名做省选题说初学OI~~
by zwuis @ 2019-03-08 21:13:15
@[lyz0](/space/show?uid=145477) 大佬别走教我A题
by salix_leaf @ 2019-03-08 21:13:50
@[salix_leaf](/space/show?uid=59700) 您tql
by GaoZiyou @ 2019-03-08 21:26:41
只拿到个省二的蒟蒻认真地说:
**不会**
**认真的**
by zwuis @ 2019-03-08 21:27:10
感谢各位大佬
以上问题已解决
是我这个几个世纪没打代码的蒟蒻把LCA打错了
```cpp
int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=17;i>=0;i--)
{
if(dep[g[i][x]]>=dep[y])
x=g[i][x];
}
if(x==y) return x;
for(int i=17;i>=0;i--)
{
if(g[0][g[i][x]]!=g[0][g[i][y]])
{
x=g[i][x];y=g[i][y];
}
}
return g[0][x];
}
```
改成
```cpp
int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=17;i>=0;i--)
{
if(dep[g[i][x]]>=dep[y])
x=g[i][x];
}
if(x==y) return x;
for(int i=17;i>=0;i--)
{
if(g[i][x]!=g[i][y])
{
x=g[i][x];y=g[i][y];
}
}
return g[0][x];
}
```
不然它可能跳到下个世纪也跳不到LCA,只能到LCA下面的一个点
by salix_leaf @ 2019-03-08 21:36:30