G.小红的树上路径查询（hard）

知识点：树上前缀和，最近公共祖先，换根dp

首先可以利用换根dp，求dp[u]表示，以u为根节点，其余所有节点到点u的总距离和

显然路径由两段构成

推导得一条链上的其中一部分贡献和(除去lca(u,v)节点父亲的贡献）为:

pre[u]：根节点到点u经过的所有点的子树大小的和

sum[u]:点u的子树中的所有节点到u的距离和

计算lca(u,v)节点父亲所带来的贡献（类似处理换根dp的思路）：

化简：

最终的ans即为两部分的贡献和

code：

void solve(int T)
{
    int n,q;
    cin>>n>>q;
    vector<vector<int>>e(n+1);
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vector f(n+1,vector<int>(20));
    vector<int>dp(n+1),son(n+1),dep(n+1),pre(n+1),fa(n+1),sum(n+1);
    auto dfs1=[&](auto &&dfs1,int u,int p)->void
    {
        son[u]=1,f[u][0]=p,dep[u]=dep[p]+1,fa[u]=p;
        for(int i=1;i<=19;i++)f[u][i]=f[f[u][i-1]][i-1];
        for(auto i:e[u])
        {
            if(i!=p)
            {
                dfs1(dfs1,i,u);
                sum[u]+=(sum[i]+son[i]);
                son[u]+=son[i];
            }
        }
    };
    auto dfs2=[&](auto &&dfs2,int u,int p)->void
    {
        for(auto i:e[u])
        {
            if(i!=p)
            {
                dp[i]=dp[u]-son[i]+n-son[i];
                pre[i]=pre[u]+son[i];
                dfs2(dfs2,i,u);
            }
        }
    };
    auto lca=[&](int u,int v)->int
    {
        if(dep[u]<dep[v])swap(u,v);
        for(int i=19;i>=0;i--)if(dep[f[u][i]]>=dep[v])u=f[u][i];
        if(u==v)return v;
        for(int i=19;i>=0;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
        return f[u][0];
    };
    dfs1(dfs1,1,0);
    dp[1]=sum[1];
    pre[1]=son[1];
    dfs2(dfs2,1,0);
    for(int i=1;i<=q;i++)
    {
        int u,v;
        cin>>u>>v;
        if(dep[u]>dep[v])swap(u,v);//让u在上
        if(u==v)cout<<dp[u]<<endl;
        else
        {
            int p=lca(u,v),ans=0;
            if(p==u)
            {
                ans=sum[p]-(pre[v]-pre[p]);
                if(fa[u])ans+=dp[fa[u]]-sum[u]-son[u]+n-son[u];
                cout<<ans<<endl;
            }
            else
            {
                if(fa[p])ans+=dp[fa[p]]-sum[p]-son[p]+n-son[p];
                ans+=sum[p]-(pre[v]-pre[p])-(pre[u]-pre[p]);
                cout<<ans<<endl;
            }
        }
    }
}