gym 101810 M. Greedy Pirate (LCA)

题目：https://codeforc.es/gym/101810/problem/M

题意：给 你一颗树，下面有m次查询，求u->v的最大值是多少，输入两点之间都会有两条边，正边有正权，反边有反权，然后问u->v可以经过的最大权值是多少

思路：我们首先以u为根我们会发现我们走非v所在子树时我们都可以把所有边走完并且回来，对于v所在子树我们也可以把正反两条边都走完，u-v的最短的那条路只能走一遍，所以这个问题就转化为了求最长链问题，u->v的最长链，但是我们有m次查询，我们不可能每次取遍历所有的点来找最长链，我们其实可以以1为根，然后用两个数组分别记录 当前点到根的距离的正反权，然后自己画图能够看出两点的距离其实就是   dis1[u]-dis1[lca(u,v)]  +  dis2[v]-dis2[lca(u,v)] 

#include<bits/stdc++.h>
using namespace std;
#define mst(ss,b) memset((ss),(b),sizeof(ss))
const int N = 1e5+5;
int t,n,m,dis[N],dis1[N],fa[N][20],fa1[N][20],dep[N],dep1[N],vs[N],vs1[N];
struct nd{
    int to,w,w1;
};
vector<nd> g[N];
 
void init() {
    for(int i=1;i<=n;i++) g[i].clear();
    mst(dis,0),mst(fa,0),mst(dep,0),mst(vs,0);
    mst(dis1,0),mst(fa1,0),mst(dep1,0),mst(vs1,0);
}
 
void dfs(int x) {///求出每个节点到根节点的距离、深度、父亲
    vs[x]=1;
    for(int i=0;i<g[x].size();i++) {
        nd tp=g[x][i];
        int v=tp.to,w=tp.w,w1=tp.w1;
        if(vs[v]) continue;
        fa[v][0]=x;
        fa1[v][0]=x;
        dis[v]=dis[x]+w;
        dis1[v]=dis1[x]+w1;
        dep[v]=dep[x]+1;
        dep1[v]=dep1[x]+1;
        dfs(v);
    }
}
 
void bz() {///倍增预处理
    for(int j=1;j<20;j++)///fa[i][j]表示结点 i 的第2^j个祖先
        for(int i=1;i<=n;i++)
            fa[i][j]=fa[fa[i][j-1]][j-1],
            fa1[i][j]=fa1[fa1[i][j-1]][j-1];
}
 
int lca(int u,int v) {
    if(dep[u]<dep[v]) swap(u,v);///注意是交换u和v,不是交换dep[u]和dep[v]
    int d=dep[u]-dep[v];
    for(int i=0;i<20;i++)///先调整到同一深度
        if(d&(1<<i)) u=fa[u][i];
    if(u==v) return u;
    for(int i=19;i>=0;i--) {///注意是倒着for，二进制拆分，从大到小尝试
        if(fa[u][i]!=fa[v][i]) {
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}
 
int main() {
    while(~scanf("%d",&t)) {
        while(t--) {
            scanf("%d",&n);
            init();
            long long ans = 0;
            for(int i=1;i<n;i++) {
                int a,b,c,d;
                scanf("%d%d%d%d",&a,&b,&c,&d);
                g[a].push_back({b,c,d});
                g[b].push_back({a,d,c});
                ans += c+d;
            }
            dep[1]=1,dis[1]=0;
            dep1[1]=1,dis1[1]=0;
            dfs(1);
            bz();
            scanf("%d",&m);
            for(int i=1;i<=m;i++) {
                int u,v;
                scanf("%d%d",&u,&v);
                printf("%lld
",ans-(dis1[v]-dis1[lca(u,v)]+dis[u]-dis[lca(u,v)]));
            }
        }
    }
    return 0;
}