題意

給定一棵 \(n\) 個點的樹，節點 \(i\) 上有 \((a_i,b_i)\) 二元組，初始時為 \((0,0)\)。\(q\) 次操作：

1. 給定 \(x,c\)，設當前是第 \(t\) 次操作，對于 \(x\) 到根節點的路徑上的每個點 \(i\)，若 \(a_i\neq c\) 則令 \((a_i,b_i)\leftarrow (c,t)\)，否則不變。
2. 給定 \(x\)，查詢 \((a_x,b_x)\)。

\(1\leq n,q\leq 10^6\)。

題解

我好菜啊。

對于每個二元組 \((a_i,b_i)\)，把 \(a_i\) 視作顏色，那么對于某個時刻 \(t\)，\(b_i\) 的就是最小的時刻使得點 \(i\) 在 \([b_i,t]\) 時刻內，顏色始終是 \(a_i\)。

離線，把每個操作 \(1\) 掛在 \(x\) 上，DFS 整棵樹轉化為維護子樹內信息。

對每個點在時間軸上開一個動態開點線段樹，節點 \([l,r]\) 維護 \(col\) 表示該點在 \(r\) 時刻的顏色，\(st\) 表示最小的時刻使得該點在 \([st,r]\) 時刻內，顏色始終是 \(col\)，\(same\) 表示 \(st\) 是否等于 \(l\)，即該點是否在時間區間內保持同色。節點很容易 \(\mathcal{O}(1)\) 合并。

DFS 到一個點的時候，加入當前點的修改操作，然后和兒子節點的線段樹做線段樹合并即可。查詢時刻 \(t\) 的二元組只需在線段樹上做前綴查詢即可。

時間復雜度 \(\mathcal{O}(q\log{q})\)。

被樹剖吊打了。

代碼

#include <iostream>
#include <vector>

using namespace std;

#define lowbit(x) ((x) & -(x))
#define chk_min(x, v) (x) = min((x), (v))
#define chk_max(x, v) (x) = max((x), (v))
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 5, N2 = N << 3;

namespace IO {
	const int S = 1 << 24, lm = 1 << 23;
	char bi[S + 5], bo[S + 5], *p1 = bi, *p2 = bi, *p3 = bo, ch;
	int s, bts, szo;
	inline char gc() { return p1 == p2 && (p2 = (p1 = bi) + fread(bi, 1, 1 << 23, stdin), p1 == p2) ? EOF : *p1++; }
	inline ll rd() {
		s = 1, bts = 0; char ch;
		while (ch = gc(), (ch < '0'));
		ll x = ch ^ 48;
		while (ch = gc(), (ch >= '0')) x = (x << 3) + (x << 1) + (ch ^ 48);
		return s == 1 ? x : -x;
	}
}
using IO::rd;

int n, q, rt[N], fa[N];
bool vis[N];
pii ans[N];
struct Op { int t, c; };
vector<Op> ops[N];
vector<int> qr[N];

struct Node {
    int st, col;
    bool same;
    Node(int s = 0, int c = 0, bool sm = 1) : st(s), col(c), same(sm) {}
    Node operator+(const Node &x) const {
        if (!col) return x;
        if (!x.col) return *this;
        if (col == x.col && x.same) return *this;
        return {x.st, x.col, 0};
    }
};
struct SegTree {
    int tot, ls[N2], rs[N2];
    Node nodes[N2];
    inline void push_up(int p) { nodes[p] = nodes[ls[p]] + nodes[rs[p]]; }
    inline void upd(int &p, int l, int r, int x, int c) {
        if (!p) p = ++tot;
        if (l == r) return nodes[p] = {x, c, 1}, void();
        int mid = l + r >> 1;
        x <= mid ? upd(ls[p], l, mid, x, c) : upd(rs[p], mid + 1, r, x, c);
        push_up(p);
    }
    inline Node query(int p, int l, int r, int x, int y) {
        if (!p) return {};
        if (x <= l && y >= r) return nodes[p];
        int mid = l + r >> 1;
        Node res;
        if (x <= mid) res = query(ls[p], l, mid, x, y);
        if (y > mid) res = res + query(rs[p], mid + 1, r, x, y);
        return res;
    }
    inline int merge(int p, int q, int l, int r) {
        if (!p || !q) return p | q;
        int mid = l + r >> 1;
        ls[p] = merge(ls[p], ls[q], l, mid), rs[p] = merge(rs[p], rs[q], mid + 1, r);
        return push_up(p), p;
    }
} sgt;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    n = rd(), q = rd();
    for (int i = 2; i <= n; ++i) fa[i] = rd();
    for (int i = 1; i <= q; ++i) {
        int op = rd(), x = rd(), c;
        if (op == 1) ops[x].push_back({i, c = rd()});
        else qr[x].push_back(i), vis[i] = 1;
    }
    for (int i = n; i; --i) {
    	int x = i;
    	for (Op &op : ops[x]) sgt.upd(rt[x], 1, q, op.t, op.c);
    	Node res;
    	for (int t : qr[x]) res = sgt.query(rt[x], 1, q, 1, t), ans[t] = {res.col, res.st};
    	if (fa[x]) rt[fa[x]] = sgt.merge(rt[fa[x]], rt[x], 1, q);
    }
    for (int i = 1; i <= q; ++i) if (vis[i]) cout << ans[i].first << ' ' << ans[i].second << '\n';
    return 0;
}