P9678 [ICPC2022 Jinan R] Tree Distance 题解

· · 题解

支配点对实在是太有意思了。

本质上就是一个合法的减枝。

思路

考虑维护树上路径问题。

容易想到点分治。

考虑在当前的分治中心 \text{rt}，每个点到当前分治中心的距离为 dp_x。

求出每一组点对的贡献。

假设每个点对在距离长的那部分贡献，即 dp_i>dp_j，求出所有的 j。

结论：每个点只需要求出符合条件下的前驱后继即可。

如何证明。

假设有 dp_j,dp_k<dp_i，k<j<i。

那么如果选了 i,k 两点，那么是绝对不如选 j,k 两点的。

后继同理。

那么我们只要在点分治时。

用一个单调栈来维护这个东西。

我们按节点编号从小到大，从大到小排序做两次，维护一个单调不降的单调栈。

每个点的前驱后继就是把它弄出栈的那个点。

把所有点对扯出来以后，可以使用扫描线和树状数组维护。

代码很好写。

Code

/**
 * @file P9678.cpp
 * @author win114514
 * @date 2023-11-25
 * 
 * @copyright Copyright (c) 2023
 * 
 */
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)
#define dbg cerr << "Line " << __LINE__ << ": "
#define EVAL(x) #x " = " << (x)

typedef int64_t i64;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
typedef pair<int, int> PII;

bool ed;

const int N = 1000010;
const int mod = 998244353;

int n, m, rt, rtsz;
int sz[N], mz[N], vs[N];
i64 t[N], dp[N], ans[N];
vector<int> son;
vector<pair<int, i64>> to[N], que[N];
vector<tuple<int, int, i64>> fin;

inline int lb(int x)
    { return x & (-x); }
inline void upd(int x, i64 v)
    { while(x <= n) t[x] = min(t[x], v), x += lb(x); }
inline i64 ask(int x)
    { i64 res = 1e17; while(x) res = min(res, t[x]), x -= lb(x); return res; }
inline void frt(int x, int fa = 0)
{
    sz[x] = 1, mz[x] = 0;
    for(auto [y, w] : to[x])
    {
        if(y == fa || vs[y]) continue;
        frt(y, x), sz[x] += sz[y];
        mz[x] = max(mz[x], sz[y]);
    }
    mz[x] = max(mz[x], rtsz - sz[x]);
    if(mz[x] < mz[rt]) rt = x;
}
inline void dfs(int x, int fa = 0)
{
    son.eb(x), sz[x] = 1;
    for(auto [y, w] : to[x])
    {
        if(y == fa || vs[y]) continue;
        dp[y] = dp[x] + w, dfs(y, x);
        sz[x] += sz[y];
    }
}
inline void calc(int x)
{
    son.clear(), dp[x] = 0, dfs(x);
    sort(son.begin(), son.end());
    static int stk[N]; int top = 0;
    for(auto i : son)
    {
        while(top && dp[stk[top]] >= dp[i])
            fin.eb(stk[top], i, dp[stk[top]] + dp[i]), top--;
        stk[++top] = i;
    }
    top = 0;
    sort(son.begin(), son.end(), greater<>());
    for(auto i : son)
    {
        while(top && dp[stk[top]] >= dp[i])
            fin.eb(stk[top], i, dp[stk[top]] + dp[i]), top--;
        stk[++top] = i;
    }
}
inline void solve(int x)
{
    vs[x] = 1, calc(x);
    for(auto [y, w] : to[x])
    {
        if(vs[y]) continue;
        rt = 0, rtsz = sz[y];
        frt(y), solve(rt);
    }
}
inline void solve()
{
    cin >> n;
    fro(i, 1, n - 1)
    {
        int x, y, w;
        cin >> x >> y >> w;
        to[x].eb(y, w), to[y].eb(x, w);
    }
    rtsz = mz[0] = n, frt(1), solve(rt);
    memset(t, 0x3f, sizeof t);
    cin >> m;
    fro(i, 1, m)
    {
        int l, r;
        cin >> l >> r;
        que[l].eb(r, i);
    }
    fro(i, 1, n) to[i].clear();
    for(auto [x, y, w] : fin)
    {
        if(x > y) swap(x, y);
        to[x].eb(y, w);
    }
    pre(i, n, 1)
    {
        for(auto [x, w] : to[i])
            upd(x, w);
        for(auto [x, id] : que[i])
            ans[id] = ask(x);
    }
    fro(i, 1, m)
        cout << (ans[i] == 1e17 ? -1 : ans[i]) << "\n";
}

bool st;

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    double Mib = fabs((&ed-&st)/1048576.), Lim = 1024;
    cerr << " Memory: " << Mib << "\n", assert(Mib<=Lim);
    solve();
    return 0;
}