原题链接

前情提要

题目不难看懂，即求a->b过程中的所有点的延迟和。显然可以暴力遍历一遍完成，但是时间复杂度太高了。

改进算法

想象这个图是由点和线组成的，把其中一个点提起来，这样就变成了一个树（n叉树），任意两点（a,b）间的延迟和等于a->lca->b，其中lca为ab两点的最近公共祖先

这样一来，只要在求lca时顺便求一下和就行了。

定值区间求和我们可以考虑用前缀和求解（前缀和太diao了）

代码

#include<bits/stdc++.h>
using namespace std;
vector<int> G[100005];
void add(int x,int y)
{
    G[x].push_back(y);
    G[y].push_back(x);
}
int fa[100005][16]={0};
int vis[100005]={0};
int depth[100005]={0};
int len[100005]={0};
int main()
{
    int n,m;
    cin>>n>>m;

    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
    }

    queue<int> q;
    q.push(1);
    vis[1]=1;
    depth[1]=1;
    len[1]=G[1].size();
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=0;i<G[now].size();i++)
        {
            int next=G[now][i];
            if(!vis[next])
            {
                fa[next][0]=now;
                vis[next]=1;
                depth[next]=depth[now]+1;
                len[next]=len[now]+G[next].size();
                q.push(next);
            }
        }
    }

    for(int k=1;k<=15;k++)
        for(int i=1;i<=n;i++)
            fa[i][k]=fa[fa[i][k-1]][k-1];




    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        if(depth[x]>depth[y])swap(x,y);

        int ans=len[x]+len[y];
        for(int i=15;i>=0;i--)
            if(depth[fa[y][i]]>=depth[x])y=fa[y][i];

        for(int i=15;i>=0;i--)
            if(fa[y][i]!=fa[x][i])
            {
                y=fa[y][i];
                x=fa[x][i];
            }

        int f=x==y?x:fa[x][0];
        cout<<ans-2*len[f]+G[f].size()<<endl;
    }
    return 0;
}