### 题目描述

• 修改给定 , ，表示点 新增了一个属性为 的物品。

• 询问给定 , , ，询问距离节点 最近的一个 "带有属性的物品" 的节点（下面称这种节点为关键节点）。

### note

```#include <bits/stdc++.h>
#define N 100005
#define inf 1000000005

using namespace std;

int n, m;
int arr[N];
int head[N], nex[N << 1], to[N << 1], eVal[N << 1], ecnt;

int x = 0;
char ch = getchar();
while (!isdigit(ch))
ch = getchar();
while (isdigit(ch))
x = x * 10 + ch - '0', ch = getchar();
return x;
}
inline void addE(int u, int v, int w) {
to[++ecnt] = v, eVal[ecnt] = w;
}

void preDfs(int u, int fa) {
for (int i = head[u], v; i; i = nex[i]) {
v = to[i];
if (v == fa)
continue;
preDfs(v, u);
}
}

int totSi***Size, curRoot;
int fa[N], siz[N], dep[N], dis[30][N];

void getDist(int u, int fa) { // get size by the way
siz[u] = 1;
for (int i = head[u], v; i; i = nex[i]) {
v = to[i];
if (v == fa || ::fa[v])
continue;
dis[dep[curRoot]][v] = dis[dep[curRoot]][u] + eVal[i];
getDist(v, u);
siz[u] += siz[v];
}
}
void getRoot(int u, int fa) {
int maxSize = 0;
for (int i = head[u], v; i; i = nex[i]) {
v = to[i];
if (v == fa || ::fa[v])
continue;
getRoot(v, u);
if (siz[v] > maxSize)
maxSize = siz[v];
}
maxSize = max(maxSize, totSize - siz[u]);
if (maxSi***Si***Size = maxSize, curRoot = u;
}
void poiDiv(int u) {
getDist(u, 0);
for(int i = head[u], v; i; i = nex[i]) {
v = to[i];
if(::fa[v])
continue;
minSize = n;
totSize = siz[v];
getRoot(v, u);
fa[curRoot] = u, dep[curRoot] = dep[u] + 1;
poiDiv(curRoot);
}
}

int totNode;
struct node {
int ch[2], fa, key;
int val, mic;
} a[N * 30];
int creNode(int key, int val) {
int u = ++totNode;
a[u].key = key, a[u].val = a[u].mic = val;
return u;
}

struct BST {
#define lch(x) (a[x].ch[0])
#define rch(x) (a[x].ch[1])
#define par(x) (a[x].fa)
int root;
void link(int u, int f, bool ind) { par(u) = f, a[f].ch[ind] = u; }
void update(int u) { a[u].mic = min(a[u].val, min(a[lch(u)].mic, a[rch(u)].mic)); }
void rotate(int u) {
int f = par(u), g = par(f);
bool ind = (a[f].ch[1] == u);
update(f);
}
void splay(int u, int tar = 0) {
int f, g;
while ((f = par(u)) != tar) {
g = par(f);
if (g != tar)
rotate((rch(g) == f) ^ (rch(f) == u) ? u : f);
rotate(u);
}
if (!tar)
root = u;
update(u);
}
void insert(int key, int val) {
int u = root, las = 0;
while (u && a[u].key != key)
las = u, u = a[u].ch[key > a[u].key];
if (!u) {
u = creNode(key, val);
} else {
a[u].val = min(a[u].val, val);
}
splay(u);
}
int pre(int key) {
int u = root, v = 0, maxKey = -1;
while (u) {
if (a[u].key < key) {
if (maxKey < a[u].key)
v = u, maxKey = a[u].key;
u = rch(u);
} else {
u = lch(u);
}
}
return v;
}
int suc(int key) {
int u = root, v = 0, minKey = N + 10;
while (u) {
if (a[u].key > key) {
if (minKey > a[u].key)
v = u, minKey = a[u].key;
u = lch(u);
} else {
u = rch(u);
}
}
return v;
}
int query(int l, int r) {
int lp = pre(l), rp = suc(r);
splay(lp), splay(rp, lp);
return a[lch(rp)].mic;
}
void init() {
root = creNode(0, inf);
}
#undef lch
#undef rch
#undef par
} Tr[N];

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

fa[1] = 1;
curRoot = 1;
poiDiv(1);
fa[1] = 0;

a[0].val = a[0].mic = inf;
for (int i = 1; i <= n; ++i)
Tr[i].init();

for(int i = 1, u; i <= n; ++i) {
u = i;
while(u) {
Tr[u].insert(arr[i], dis[dep[u]][i]);
u = fa[u];
}
}

for (int i = 1, op, x, l, r; i <= m; ++i) {
if (op == 1) {
int u = x;
while(u) {
Tr[u].insert(l, dis[dep[u]][x]);
u = fa[u];
}
} else {