【题意】给了一颗树，问加一条边可以为两点节省多少距离？

【解题方法】知道dp[u,v]=dp[u]+dp[v]-2*dp[lca(u,v)]就没问题啦。

【AC 代码】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int n,q,a,b,l;
int head[maxn],tot,dp[maxn],p[18][maxn],dep[maxn];
struct edge{
    int v,w,next;
}E[maxn<<2];
void init(){
    memset(head,-1,sizeof(head));tot=0;
}
void addedge(int u,int v,int w){
    E[tot].v=v,E[tot].w=w,E[tot].next=head[u],head[u]=tot++;
}
void dfs(int u,int f,int c,int d)
{
    dep[u]=d;
    p[0][u]=f;
    dp[u]=c;
    for(int i=head[u]; ~i; i=E[i].next){
        int v=E[i].v;
        if(v==f) continue;
        dfs(v,u,c+E[i].w,d+1);
    }
}
void build()
{
    dfs(1,-1,0,0);
    for(int i=0; i+1<18; i++){
        for(int v=1; v<=n; v++){
            if(p[i][v]<0) p[i+1][v] = -1;
            else p[i+1][v]=p[i][p[i][v]];
        }
    }
}
int lca(int u,int v)
{
    if(dep[u]>dep[v]) swap(u,v);
    for(int i=0; i<18; i++){
        if(dep[v]-dep[u]>>i&1) v=p[i][v];
    }
    if(u==v) return u;
    for(int i=17; i>=0; i--){
        if(p[i][u]!=p[i][v]){
            u=p[i][u];
            v=p[i][v];
        }
    }
    return p[0][u];
}
int main()
{
    int T,cas=1;
    int u,v,w;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d%d",&n,&q);
        for(int i=1; i<n; i++){
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            addedge(v,u,w);
        }
        build();
        scanf("%d%d%d",&a,&b,&l);
        printf("Case #%d:\n",cas++);
        while(q--)
        {
            scanf("%d%d",&u,&v);
            int _lca=lca(u,v);
            int uv = dp[u]+dp[v]-2*dp[_lca];
            int ua = dp[u]+dp[a]-2*dp[lca(u,a)];
            int ub = dp[u]+dp[b]-2*dp[lca(u,b)];
            int av = dp[a]+dp[v]-2*dp[lca(a,v)];
            int bv = dp[b]+dp[v]-2*dp[lca(b,v)];
            int ans = max(0,uv-min(ua+bv,ub+av)-l);
            printf("%d\n",ans);
        }
    }
    return 0;
}