[Ynoi2004] rpmtdq 题解-526互联

人生第一发 \(Ynoi\) 的题, 写一篇题解庆祝一下

传送门

我们可以发现, 对于二元组 \((x, y)\) , 若存在一个 \(dist(i, j) \le dist(x, y), x < i < j < y\) 那么答案肯定不是二元组 \((x, y)\)

我们可以考虑把这些肯定不是的点剔除掉

考虑怎么找, 我们可以先点分治, 求出每个点到当前分治中心 \(root\) 的 \(dist(root, v)\) 记为 \(dis(v)\)

对于 \(i\) 与 \(j\) 这一对点对, ( \(i < k < j\) )

有 \(dis[i] + dis[j] < dis[k] + dis[j]\) 即 \(dis[i] < dis[k]\) 时,

并且 \(dis[i] + dis[j] < dis[i] + dis[k]\) 即 \(dis[j] < dis[k]\) 时,

它才有可能成为答案, 其余情况都不能成为答案

简单来说就是两边的都小于中间, 我们可以规定 \(dis[j] > dis[i]\) 对于 \(j\) 来说, 我们要找的就是第一个 小于等于 \(dis[j]\) 的 \(dis[i]\) , 我们可以用单调栈实现, 对于 \(dis[i] > dis[j]\) 的情况, 可以反着再跑一边单调栈

复杂度: \(O(nlog^2n)\)

点分治一共 \(logn\) 层, 每一层每个点会贡献一次, 所以点对数量为 \(nlogn\) 个

点对的真实值可以用 \(lca\) 和差分求一下

最后将询问离线, 做类似于扫描线的二维数点就可以了

可以用树状数组实现

树状数组的实现有一点不一样

修改最小值向下传递, 查询最小值向上传递, 因为我要查询 \(x - r\) , 所以反了过来

最主要的是, 要发现, 其中有一些点是肯定不能成为答案的, 这样可以大大缩减点对的数量


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < ll, ll > pai;
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int INF = 1e9;
const ll INF_ = 1e18;

int n, q, head[N], egtot, siz[N], top;
bool del[N];
ll ans[M];
pai stk[N], stk2[N];
int top2;
vector < int > use[N];

struct Edge {
    int to, nxt, w;
} a[N << 1];
struct Query {
    int l, id;
};

vector<Query>qr[N];

inline ll read() {
	ll x = 0;
	char ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
}

void add(int u, int v, int w) {

    a[++egtot].to = v;
    a[egtot].nxt = head[u];
    a[egtot].w = w;
    head[u] = egtot;
}

void push(int u, int v) {
    if (u > v)
        swap(u, v);
    use[v].push_back(u);
}

pai findroot(int rt, int f, int pre) {
    siz[rt] = 1;
    int mx = 0;
    pai ans = make_pair(INF, 0);
    for (int i = head[rt]; i; i = a[i].nxt) {
        int t = a[i].to;
        if (del[t] || t == f)
            continue;
        ans = min(ans, findroot(t, rt, pre));
        siz[rt] += siz[t];
        mx = max(mx, siz[t]);
    }
    ans = min(ans, make_pair(max(ll(mx), ll(pre - siz[rt])), ll(rt)));
    return ans;
}

void dfs(int rt, int f, ll s) {
    stk[++top] = make_pair(rt, s);
    for (int i = head[rt]; i; i = a[i].nxt) {
        int t = a[i].to;
        if (t == f || del[t])
            continue;
        dfs(t, rt, s + a[i].w);
    }
}

void solve(int rt, int pre) {
    int root = findroot(rt, 0, pre).second;
    int res = siz[rt];
    del[root] = 1;
    top = 0;
    for (int i = head[root]; i; i = a[i].nxt) {
        int t = a[i].to;
        if (del[t])
            continue;
        dfs(t, root, a[i].w);
    }
    stk[++top] = make_pair(root, 0);
    sort(stk + 1, stk + top + 1);
    top2 = 0;
    for (int i = 1; i <= top; i++) {
        int id = stk[i].first;
        ll d = stk[i].second;
        while (top2 && stk2[top2].second > d)
            top2--;
        push(id, stk2[top2].first);
        stk2[++top2] = stk[i];
    }
    top2 = 0;
    for (int i = top; i >= 1; i--) {
        int id = stk[i].first;
        ll d = stk[i].second;
        while (top2 && stk2[top2].second > d)
            top2--;
        push(id, stk2[top2].first);
        stk2[++top2] = stk[i];
    }
    for (int i = head[root]; i; i = a[i].nxt) {
        int t = a[i].to;
        if (del[t])
            continue;
        solve(t, res);
    }
}

int dep[N], ind[N], lg[N << 1], cnt, st[20][N << 1];
ll de[N];
void dfs(int rt, int f) {
    dep[rt] = dep[f] + 1;
    st[0][++cnt] = rt, ind[rt] = cnt;

    for (int i = head[rt]; i; i = a[i].nxt) {
        int t = a[i].to;
        if (t == f)
        	continue;
        de[t] = de[rt] + a[i].w;
        dfs(t, rt);
        st[0][++cnt] = rt;
    }
}

int cmp(int x, int y) {
    return dep[x] < dep[y] ? x : y;
}

void init() {
    dfs(1, 0);
    for (int i = 1; (1 << i) <= cnt; i++)
        for (int j = 1; j + (1 << i) - 1 <= cnt; j++)
            st[i][j] = cmp(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
    for (int i = 2; i <= cnt; i++)
        lg[i] = lg[i >> 1] + 1;
}

int LCA (int x, int y) {
    x = ind[x], y = ind[y];
    if (x > y)
        swap(x, y);
    int i = lg[y - x + 1];
    int p = 1 << i;
    return cmp(st[i][x], st[i][y - p + 1]);
}

ll dis(int x, int y) {
    return de[x] + de[y] - 2 * de[LCA(x, y)];
}

struct Tree {
    ll t[N];
    int lowbit (int x) {
    	return x & (-x);
	}
	
    void init() {
        for (int i = 1; i <= n; i++)
            t[i] = INF_;
    }
    
    void add(int p, ll v) {
        for (int i = p; i; i -= lowbit(i))
            t[i] = min(t[i], v);
    }
    
    ll query(int p) {
        ll ans = INF_;
        for (int i = p; i <= n; i += lowbit(i))
            ans = min(ans, t[i]);
        return ans;
    }
} T;

int main() {
    n = read();

    for (int i = 1, u, v, w; i < n; i++) {
        u = read(); v = read(); w = read();
        add(u, v, w), add(v, u, w);
    }

    solve(1, n);
    init();
    T.init();
    q = read();

    for (int i = 1, l, r; i <= q; i++) {
        l = read(); r = read();
        if (l >= r) ans[i] = -1;
        else qr[r].push_back((Query) {l, i});
    }

    for (int i = 1; i <= n; i++) {
        sort(use[i].begin(), use[i].end());
        use[i].resize(unique(use[i].begin(), use[i].end()) - use[i].begin());
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < int(use[i].size()); j++)
            T.add(use[i][j], dis(use[i][j], i));
        for (int j = 0; j < int(qr[i].size()); j++)
            ans[qr[i][j].id] = T.query(qr[i][j].l);
    }

    for (int i = 1; i <= q; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

rpmtdq p9058 2004 ynoi