奈特公司有着庞大的情报网络。情报网络中共有 名情报员。每名情报员有若干名下线，除 1 名大头目外其余 名情报员有且仅有 1 名上线。每名情报员只能与自己的上、下线联系，同时，情报网络中任意两名情报员一定能够通过情报网络传递情报。奈特公司每天会派发以下两种任务中的一个任务：
- 搜集情报：指派 号情报员搜集情报；
- 传递情报：将一条情报从 号情报员传递给 号情报员。
情报员最初处于潜伏阶段，危险值为 0；一旦某个情报员开始搜集情报，他的危险值就会持续增加，每天增加 1 点危险值（开始搜集情报的当天危险值仍为 0，第 2 天危险值为 1，以此类推）。传递情报并不会使情报员的危险值增加。
为了保证传递情报的过程相对安全，每条情报都有一个风险控制值 。公司认为，传递这条情报的所有情报员中，危险值大于 的情报员将对该条情报构成威胁。现在，奈特公司希望知道，对于每个传递情报任务，参与传递的情报员有多少个，其中对该条情报构成威胁的情报员有多少个。
链接
题解
因为整个网络是一棵树，所以可以用一棵 Link-Cut Tree 来维护。
前 30 分，无修改操作，直接求出两点距离。
30 ~ 60 分，保证 ，修改直接单点修改值为 1，查询直接查询有多少 1 即可。
后 40 分，考虑到对于每个查询操作，只有距离它 天之前的修改操作对它有贡献，所以可以将操作离线，保证每次修改后直接处理查询即可。
代码
#include <cstdio>
#include <climits>
#include <queue>
#include <algorithm>
const int MAXN = 200000;
const int MAXM = 200000;
struct LinkCutTree {
enum Relation {
L = 0, R = 1
};
struct Node {
Node *child[2], *parent, *pathParent;
int value, sum, size;
bool reversed;
Node() : parent(NULL), pathParent(NULL), value(0), sum(0), size(1), reversed(false) {
child[L] = child[R] = NULL;
}
void pushDown() {
if (reversed) {
std::swap(child[L], child[R]);
if (child[L]) child[L]->reversed ^= 1;
if (child[R]) child[R]->reversed ^= 1;
reversed = false;
}
}
void maintain() {
sum = value, size = 1;
if (child[L]) sum += child[L]->sum, size += child[L]->size;
if (child[R]) sum += child[R]->sum, size += child[R]->size;
}
Relation relation() {
return this == parent->child[L] ? L : R;
}
void rotate() {
if (parent->parent) parent->parent->pushDown();
parent->pushDown(), pushDown();
std::swap(pathParent, parent->pathParent);
Relation x = relation();
Node *oldParent = parent;
if (oldParent->parent) oldParent->parent->child[oldParent->relation()] = this;
parent = oldParent->parent;
if (child[x ^ 1]) child[x ^ 1]->parent = oldParent;
oldParent->child[x] = child[x ^ 1];
child[x ^ 1] = oldParent;
oldParent->parent = this;
oldParent->maintain(), maintain();
}
void splay() {
while (parent != NULL) {
if (parent->parent == NULL) rotate();
else {
parent->parent->pushDown(), parent->pushDown();
if (parent->relation() == relation()) parent->rotate(), rotate();
else rotate(), rotate();
}
}
pushDown();
}
void expose() {
splay();
if (child[R]) {
std::swap(child[R]->parent, child[R]->pathParent);
child[R] = NULL;
maintain();
}
}
bool splice() {
splay();
if (!pathParent) return false;
pathParent->expose();
pathParent->child[R] = this;
pathParent->maintain();
std::swap(parent, pathParent);
return true;
}
void access() {
expose();
while (splice());
}
void evert() {
access();
splay();
reversed ^= 1;
}
} nodes[MAXN];
void query(int u, int v, int &size, int &sum) {
nodes[u - 1].evert();
nodes[v - 1].access();
nodes[v - 1].splay();
size = nodes[v - 1].size;
sum = nodes[v - 1].sum;
}
void update(int u, int value) {
nodes[u - 1].splay();
nodes[u - 1].value = value;
nodes[u - 1].maintain();
}
void link(int u, int v) {
nodes[v - 1].evert();
nodes[v - 1].splay();
nodes[v - 1].pathParent = &nodes[u - 1];
}
} lct;
struct Day {
int id;
int task;
int u, v, c;
bool operator<(const Day &other) const {
return c < other.c;
}
} days[MAXM];
int n, m;
inline void bfs() {
std::queue<Tree *> q;
q.push(&nodes[0]);
nodes[0].depth = 1;
while (!q.empty()) {
Tree *t = q.front();
q.pop();
for (Tree *c = t->firstChild; c; c = c->next) {
c->depth = t->depth + 1;
q.push(c);
}
}
}
inline void work() {
for (int i = 0; i < m; i++) {
if (days[i].task == 2) lct.update(days[i].u, 1);
else {
int size, sum;
lct.query(days[i].u, days[i].v, size, sum);
printf("%d %d\n", size, sum);
}
}
}
int main() {
// freopen("message.in", "r", stdin);
// freopen("message.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int u;
scanf("%d", &u);
if (u != 0) lct.link(u, i);
}
scanf("%d", &m);
bool flag1 = true, flag2 = true;
for (int i = 0; i < m; i++) {
days[i].id = i;
scanf("%d", &days[i].task);
if (days[i].task == 2) scanf("%d", &days[i].u), days[i].c = i;
else {
int tmp;
scanf("%d %d %d", &days[i].u, &days[i].v, &tmp);
days[i].c = i - tmp;
}
}
std::sort(days, days + m);
work();
fclose(stdin);
fclose(stdout);
return 0;
}