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+;

int t,n,m,dis[N],dis1[N],fa[N][],fa1[N][],dep[N],dep1[N],vs[N],vs1[N];

struct nd{

    int to,w,w1;

};

vector<nd> g[N];

void init() {

    for(int i=;i<=n;i++) g[i].clear();

    mst(dis,),mst(fa,),mst(dep,),mst(vs,);

    mst(dis1,),mst(fa1,),mst(dep1,),mst(vs1,);

}

void dfs(int x) {///求出每个节点到根节点的距离、深度、父亲

    vs[x]=;

    for(int i=;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][]=x;

        fa1[v][]=x;

        dis[v]=dis[x]+w;

        dis1[v]=dis1[x]+w1;

        dep[v]=dep[x]+;

        dep1[v]=dep1[x]+;

        dfs(v);

    }

}

void bz() {///倍增预处理

    for(int j=;j<;j++)///fa[i][j]表示结点 i 的第2^j个祖先

        for(int i=;i<=n;i++)

            fa[i][j]=fa[fa[i][j-]][j-],

            fa1[i][j]=fa1[fa1[i][j-]][j-];

}

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=;i<;i++)///先调整到同一深度

        if(d&(<<i)) u=fa[u][i];

    if(u==v) return u;

    for(int i=;i>=;i--) {///注意是倒着for，二进制拆分，从大到小尝试

        if(fa[u][i]!=fa[v][i]) {

            u=fa[u][i];

            v=fa[v][i];

        }

    }

    return fa[u][];

}

int main() {

    while(~scanf("%d",&t)) {

        while(t--) {

            scanf("%d",&n);

            init();

            long long ans = ;

            for(int i=;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[]=,dis[]=;

            dep1[]=,dis1[]=;

            dfs();

            bz();

            scanf("%d",&m);

            for(int i=;i<=m;i++) {

                int u,v;

                scanf("%d%d",&u,&v);

                printf("%lld\n",ans-(dis1[v]-dis1[lca(u,v)]+dis[u]-dis[lca(u,v)]));

            }

        }

    }

    return ;

}