题目地址：Codeforces：Problem – 100633D – Codeforces

题目描述

The Large Wood Database is created to securely store and paint any existing tree. Update for LWDB provides new functionality, so it is time to think over the graph theory. A weighed tree is stored in the LWDB. In the query language for LWDB Management System (LWDB MS) two types of queries are available:

1. «1 v d c» — paint all tree-vertices at the distance not exceeding d from the vertice v in color c. Initial color for any vertices is 0.
2. «2 v» — return the color of the vertice v.

It is required to prototype LWDB MS and respond to all user’s queries.
给你一棵带边权的树，要求操作1.改变一个节点d距离内的所有点颜色为c；2.询问一个点颜色。

输入输出格式

输入格式：
The first line contains an integer N (1 ≤ N ≤ 105) — the number of tree vertices. The following N-1 lines contain the description of branches, three numbers in each line ai, bi, wi (1 ≤ ai, bi ≤ N, ai ≠ bi, 1 ≤ wi ≤ 104), where i-th branch with weight wi connects vertices ai and bi. The next line contains integer Q (1 ≤ Q ≤ 105) — number of queries. In each of Q following lines there are two types of queries:

1. Numbers 1, v, d, c (1 ≤ v ≤ N, 0 ≤ d ≤ 109, 0 ≤ c ≤ 109).
2. Numbers 2, v (1 ≤ v ≤ N).

Input numbers are integers.

输出格式：
For each second type query output the color of requested vertice in a separate line.

输入输出样例

输入样例#1：

5
1 2 30
1 3 50
3 4 70
3 5 60
8
1 3 72 6
2 5
1 4 60 5
2 3
2 2
1 2 144 7
2 4
2 5

输出样例#1：

6
6
0
5
7

题解

对于这道题，我们在点分树上统计的信息变成了每一次染色操作。
对于一个距离为d，染色点为u的染色操作，我们在它到树根这条链上的重心打标记，直到u到某个重心的距离超出了染色距离。标记的含义是，从这个重心出发的若干距离范围内的点都被打上标记。在每个重心维护一个单调栈，使得栈内标记的作用范围d以时间顺序单调递减。
查询时，也从查询点u往根走，二分找到能影响到这个点的标记，维护当前找到的最新标记，该标记就是最终给这个点染色的标记。
可以脑补一下这个过程来意识流证明其正确性。

代码

下面的代码参考了【Codeforces 100633D】LWDB – Qizy’s Database。Qizy同学的代码还是非常优美的。利用预处理和倍增减小常数，实现的抽象和封装也很优美。学习了。

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <vector>
#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

int fa[MAXN][20], dep[MAXN], dis[MAXN];

struct Edge {
    int to, w;
};
std::vector<Edge> gra[MAXN];

inline void dfs(int u, int f) {
    fa[u][0] = f;
    dep[u] = dep[f] + 1;
    for(Edge e : gra[u]) {
        int v = e.to, w = e.w;
        if(v == f) continue;
        dis[v] = dis[u] + w;
        dfs(v, u);
    }
}

inline int caldis(int u, int v) {
    int res = dis[u] + dis[v];
    if(dep[u] < dep[v]) std::swap(u, v);
    for(int i = 19; i >= 0; i--) {
        if(dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    }
    if(u == v) return res - (dis[u] << 1);
    for(int i = 19; i >= 0; i--) {
        if(fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return res - (dis[fa[u][0]] << 1);
}

int sum, rt, rod[MAXN][20], siz[MAXN], msz[MAXN], anc[MAXN][20], len[MAXN];
bool vis[MAXN];

struct Data {
    int dis, col, id;
    inline bool operator<(const Data &rhs) const {
        return dis < rhs.dis;
    }
    inline bool operator<=(const Data &rhs) const {
        return dis <= rhs.dis;
    }
};

Data tmp;
std::vector<Data> stk[MAXN];
std::vector<Data>::reverse_iterator it;

inline void getrt(int u, int fa) {
    siz[u] = 1;
    msz[u] = 0;
    for(Edge e : gra[u]) {
        int v = e.to;
        if(v == fa || vis[v]) continue;
        getrt(v, u);
        siz[u] += siz[v];
        msz[u] = std::max(msz[u], siz[v]);
    }
    msz[u] = std::max(msz[u], sum - siz[u]);
    if(msz[u] < msz[rt]) rt = u;
}

inline void dac(int u) {
    anc[u][0] = u;
    vis[u] = true;
    for(Edge e : gra[u]) {
        int v = e.to;
        if(vis[v]) continue;
        sum = siz[v];
        rt = 0;
        getrt(v, u);
        len[rt] = len[u] + 1;
        memcpy(anc[rt] + 1, anc[u], sizeof(anc[u]) - 4);
        dac(rt);
    }
    for(int i = 1; i < len[u]; i++) {
        rod[u][i] = caldis(u, anc[u][i]);
    }
}

inline void modify(int u, int d, int col, int id) {
    tmp.col = col; tmp.id = id;
    for(int i = 0; i < len[u]; i++) {
        int f = anc[u][i];
        tmp.dis = d - rod[u][i];
        if(tmp.dis >= 0) {
            while(!stk[f].empty() && stk[f].back() <= tmp) stk[f].pop_back();
            stk[f].push_back(tmp);
        }
    }
}

inline int query(int u) {
    Data res = {0, 0, 0};
    for(int i = 0; i < len[u]; i++) {
        int f = anc[u][i]; tmp.dis = rod[u][i];
        it = std::lower_bound(stk[f].rbegin(), stk[f].rend(), tmp);
        if(it != stk[f].rend() && res.id < it->id) res = *it;
    }
    return res.col;
}

int n, ut, vt, wt, m, op, dt, ct;

int main() {
    n = readint();
    for(int i = 1; i < n; i++) {
        ut = readint(); vt = readint(); wt = readint();
        gra[ut].push_back(Edge {vt, wt});
        gra[vt].push_back(Edge {ut, wt});
    }
    dfs(1, 1);
    for(int k = 1; k < 20; k++) {
        for(int i = 1; i <= n; i++) {
            fa[i][k] = fa[fa[i][k - 1]][k - 1];
        }
    }
    msz[0] = INF;
    sum = n;
    rt = 0;
    getrt(1, 0);
    len[rt] = 1;
    dac(rt);
    m = readint();
    for(int i = 1; i <= m; i++) {
        op = readint();
        if(op == 1) {
            ut = readint(); dt = readint(); ct = readint();
            modify(ut, dt, ct, i);
        } else {
            ut = readint();
            printf("%d\n", query(ut));
        }
    }
    return 0;
}