周赛 辛勤的蚂蚁 题解（LCA）

题目链接

题目思路

显然是在树上找最短路的问题，那么就要想到lca

因为所有由 s->t的路径我们都能看成 s ->lca(s,t)->t。很明显 s->lca(s,t) 和 lca(s,t)->t 都是一条链。

关键 ：L( s ,t )=depth( s )+depth( t )-2*depth ( lca ( s , t ) )

最后要注意分类讨论即可，由于每两个点的距离都是1所以直接用深度代替长度即可，完全没有必要再去开一个数组

易错警示

无向边一定要开两倍大小（找了2小时bug，最主要是学校oj神助攻，居然会把re报错成tle）

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=3e5+5;
int n,m,k,head[maxn],cnt,u,v,lg[maxn],fa[maxn][30],depth[maxn],last[maxn];
struct node
{
    int to,next;
}e[maxn<<1];
void add(int u,int v)//链式前向星建图
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int son,int father)//预处理
{
    fa[son][0]=father;
    depth[son]=depth[father]+1;
    for(int i=1;i<=lg[depth[son]];i++)
    {
        fa[son][i]=fa[fa[son][i-1]][i-1];
    }
    for(int i=head[son];i;i=e[i].next)
    {
        if(e[i].to!=father)
        {
            dfs(e[i].to,son);
        }
    }
}
int lca(int x,int y)//lca板子
{
    if(depth[x]<depth[y])
        swap(x,y);
    while(depth[x]>depth[y])
    {
        x=fa[x][lg[depth[x]-depth[y]]-1];
    }
    if(x==y)
        return x;
    for(int k=lg[depth[x]]-1;k>=0;k--)
    {
        if(fa[x][k]!=fa[y][k])
        {
            x=fa[x][k],y=fa[y][k];
        }
    }
    return fa[x][0];
}
int main()
{
    for(int i=1;i<=3e5;i++)//log2(i)+1
    {
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        int dad=lca(u,v);
        if(depth[u]+depth[v]-2*depth[dad]<=k)//在终点
        {
            last[v]++;
        }
        else if(depth[u]-depth[dad]>=k)//在左边
        {
            int len=depth[u]-k;//终点深度
            while(depth[u]>len)
            {
                u=fa[u][lg[depth[u]-len]-1];
            }
            last[u]++;
        }
        else//在右边
        {
            int len=depth[v]-(depth[v]-depth[dad]-(k-(depth[u]-depth[dad])));//右链需要往上爬的长度为右链长-(k-左链的长度)
            //len代表终点深度
            while(depth[v]>len)
            {
                v=fa[v][lg[depth[v]-len]-1];
            }
            last[v]++;
        }
    }
    for(int i=1;i<n;i++)
    {
        printf("%d ",last[i]);
    }
    printf("%d",last[n]);
    return 0;
}