CodeForces 101810M :Greedy Pirate LCA

CodeForces 101810M :Greedy Pirate LCA

传送门

题目描述

有 n n n个点, n − 1 n-1 n−1条边,每条边正向和反向有两个权值,且每条边最多只能走两次,有 m m m次询问,问你从 u u u走到 v v v的最大权值是多少.

分析

李巨送来的好题
画个图分析一下，从 u u u到 v v v的路径是唯一的，也就是说我如果走过去了就不可能再回来了，而其他的点可以走过去再回来，也就是说答案就是所有边的权值减去 u u u到 v v v的反向路径的权值
那么我们怎么去求这个反向路径呢，用LCA可以很快的解决这个先预处理出来每一个点到根节点的正向距离和反向距离，然后根据 u , v u,v u,v到LCA的关系处理一下即可

代码

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lldn",x);
#define di(x) printf("%dn",x);
#define _CRT_SECURE_NO_WARNINGS
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10,M = N * 2;
const ll mod = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a) {char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}
int gcd(int a, int b) {return (b > 0) ? gcd(b, a % b) : a;}
int h[N],ne[M],e[M],idx;
int w1[M],w2[M];
int d[N],f[N][25];
int d1[N],d2[N];
int n,m;void add(int a,int b,int c1,int c2){ne[idx] = h[a],e[idx] = b,w1[idx] = c1,w2[idx] = c2,h[a] = idx++;
}void bfs(int root){for(int i = 1;i <= n;i++) d[i] = INF;d[0] = 0,d[root] = 1;d1[1] = d2[1] = 0;queue<int> Q;Q.push(root);while(Q.size()){int t = Q.front();Q.pop();for(int i = h[t];~i;i = ne[i]){int j = e[i];if(d[j] > d[t] + 1){d[j] = d[t] + 1;Q.push(j);f[j][0] = t;d2[j] = d2[t] + w2[i];d1[j] = d1[t] + w1[i];for(int k = 1;k <= 20;k++)f[j][k] = f[f[j][k - 1]][k - 1];}}}
}int LCA(int a,int b){if(d[a] < d[b]) swap(a,b);for(int i = 20;i >= 0;i--)if(d[f[a][i]] >= d[b])a = f[a][i];if(a == b) return a;for(int i = 20;i >= 0;i--)if(f[a][i] != f[b][i])a = f[a][i],b = f[b][i];return f[a][0];
}int main() {int T;read(T);while(T--){read(n);for(int i = 1;i <= n;i++) h[i] = -1;int sum = 0;for(int i = 1;i < n;i++){int x,y,z1,z2;read(x),read(y),read(z1),read(z2);add(x,y,z1,z2);add(y,x,z2,z1);sum += z1 + z2;}int q;read(q);bfs(1);while(q--){int x,y;read(x),read(y);int ans = sum - (d1[x] + d2[y] - d1[LCA(x,y)] - d2[LCA(x,y)]);di(ans);}}return 0;
}/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/