[牛客网#35D 树的距离]离散化+线段树合并

分类：Data Structure SegMent Tree Merge

1. 题目链接

[牛客网#35D 树的距离]

2. 题意描述

wyf非常喜欢树。一棵有根数树上有n个节点，1号点是他的根，每条边都有一个距离，而wyf是个爱问奇怪问题的熊孩子，他想知道对于某个点x,以x为根的子树上，所有与x距离大于等于k的点与x的距离之和。
数据范围：1≤n,q≤2∗105,1≤d,k≤106

3. 解题思路

同《[Codeforces 893F. Subtree Minimum Query]线段树合并》这题的思路。
通过这两个题目总算对线段树合并比较理解了。
对每个节点建一个线段树，维护每个距离出现的次数以及区间距离之和。

4. 实现代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double lb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> puu;
typedef pair<lb, lb> pbb;
typedef vector<int> vi;

const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
template<typename T> inline void umax(T &a, T b) { a = max(a, b); }
template<typename T> inline void umin(T &a, T b) { a = min(a, b); }
template<typename T> inline T randIntv(const T& a, const T& b) { return (T)rand() % (b - a + 1) + a; }
void debug() { cout << endl; }
template<typename T, typename ...R> void debug (T f, R ...r) { cout << "[" << f << "]"; debug (r...); }

const int MAXN = 200005;
int n, q;
struct Edge {
    int v, next;
    ll w;
} edge[MAXN << 1];
int head[MAXN], etot;
void ini(int n) {
    etot = 0;
    for (int i = 0; i <= n; ++i) head[i] = -1;
}
void ins(int u, int v, ll w) {
    edge[etot].v = v;
    edge[etot].w = w;
    edge[etot].next = head[u];
    head[u] = etot ++;
}

struct TNode {
    int cnt;
    ll sum;
    int ch[2];
    void ini() { cnt = sum = ch[0] = ch[1] = 0; }
} nd[MAXN * 50];
int root[MAXN], nsz, null = 0;
ll dep[MAXN];
ll f[MAXN], fsz;
#define lch     nd[rt].ch[0]
#define rch     nd[rt].ch[1]
void pushUp(int rt) {
    nd[rt].cnt = nd[lch].cnt + nd[rch].cnt;
    nd[rt].sum = nd[lch].sum + nd[rch].sum;
}
void update(int p, ll v, int l, int r, int& rt) {
    nd[rt = ++ nsz].ini();
    if (l == r) {
        nd[rt].cnt = 1;
        nd[rt].sum = v;
        return;
    }
    int md = (l + r) >> 1;
    if (p <= md) update(p, v, l, md, lch);
    else update(p, v, md + 1, r, rch);
    pushUp(rt);
}
int merge(int u, int v) {
    if (!u || !v) return u ^ v;
    int rt = ++ nsz; nd[rt].ini();
    nd[rt].ch[0] = merge(nd[u].ch[0], nd[v].ch[0]);
    nd[rt].ch[1] = merge(nd[u].ch[1], nd[v].ch[1]);
    nd[rt].cnt = nd[u].cnt + nd[v].cnt;
    nd[rt].sum = nd[u].sum + nd[v].sum;
    return rt;
}

void dfs1(int u, int fa, ll d) {
    dep[u] = d;
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].v; ll w = edge[i].w;
        if (v == fa) continue;
        dfs1(v, u, d + w);
    }
}

void dfs2(int u, int fa) {
    int pos = lower_bound(f + 1, f + fsz + 1, dep[u]) - f;
    update(pos, dep[u], 1, fsz, root[u]);
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa) continue;
        dfs2(v, u);
        root[u] = merge(root[u], root[v]);
    }
}

pair<int, ll> query(int L, int R, int l, int r, int rt) {
    // if (L <= l && r <= R) debug("query", rt, nd[rt].cnt, nd[rt].sum);
    if (L <= l && r <= R) return make_pair(nd[rt].cnt, nd[rt].sum);
    int md = (l + r) >> 1;
    pair<int, ll> lop(0, 0), rop(0, 0);
    if (L <= md) lop = query(L, R, l, md, lch);
    if (R > md) rop = query(L, R, md + 1, r, rch);
    return make_pair(lop.first + rop.first, lop.second + rop.second);
}

int main() {
#ifdef ___LOCAL_WONZY___
    freopen("input.txt", "r", stdin);
#endif // ___LOCAL_WONZY___
    int u, x, cnt; ll w, k, sum, ans;
    while (~scanf("%d", &n)) {
        ini(n);
        for (int i = 2; i <= n; ++i) {
            scanf("%d %lld", &u, &w);
            ins(i, u, w), ins(u, i, w);;
        }
        nsz = null = 0;
        dfs1(1, 1, 1);
        for (int i = 1; i <= n; ++i) f[i] = dep[i];
        sort(f + 1, f + n + 1);
        fsz = unique(f + 1, f + n + 1) - (f + 1);
        dfs2(1, 1);
        scanf("%d", &q);
        for (int i = 1; i <= q; ++i) {
            scanf("%d %lld", &x, &k);
            int pos = lower_bound(f + 1, f + fsz + 1, dep[x] + k) - f;
            tie(cnt, sum) = query(pos, fsz, 1, fsz, root[x]);
            ans = sum - cnt * dep[x];
            // debug(cnt, sum, ans);
            printf("%lld\n", ans);
        }
    }
#ifdef ___LOCAL_WONZY___
    cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC * 1000 << "ms." << endl;
#endif // ___LOCAL_WONZY___
    return 0;
}