[传智杯 #4 初赛] 小卡与落叶
题目背景
坐在飞驰的火车上,望着窗外泛黄的树叶,“又是一个冬天”,小卡心想。这是一个万物凋零的季节,一阵寒风刮过,树叶就被染黄了,再一阵寒风刮过,便是满地金黄。
百无聊赖之际,小卡发现,树叶变黄是有规律的,每一颗树,只有下面一半是黄的,上半部分都是绿的。小卡心想,该怎么统计黄色的叶子个数呢?
题目描述
给你一棵有 $n(1\le n\le 10^5)$ 个结点的有根树,根结点标号为 $1$,根节点的深度为 $1$,最开始整棵树的所有结点都是绿色的。
小卡有 $m(1\le m \le 10^5)$ 个操作。
操作一:把整棵树都染绿,之后让深度 $\ge x$ 的结点变黄。
操作二:询问一个结点 $x$ 的子树中有多少个黄色结点。
输入格式
第一行两个正整数 $n,m$,表示树的结点个数和操作个数。
接下来 $n-1$ 行,每行两个正整数 $x,y$,表示树上的一条边。
接下来 $m$ 行,每行两个正整数 $op,x(1\le x\le n)$,如果 $op=1$ 则表示操作一,否则表示操作二。
输出格式
对于每个操作二,输出一行一个正整数,表示 $x$ 的子树中黄色结点的个数。
样例 #1
样例输入 #1
5 9
1 2
1 3
2 4
4 5
1 3
2 5
2 2
2 1
1 2
2 1
2 4
2 5
2 2
样例输出 #1
1
2
2
4
2
1
3
提示
样例一中的树如下:
第一次染色将 $4$ 和 $5$ 染为黄色,查询 $5,2,1$ 三个点的子树,答案分别为 $1,2,2$。
第二次染色将 $2,3,4,5$ 染为黄色,查询 $1,4,5,2$ 四个点的子树,答案分别为 $4,2,1,3$。
题目分析
不难把每个询问转化成以下形式:
查询以 $x$ 为根的树当中深度 $≥d$ 的个数。
我们可以先把所有询问离线下来,按照 $d$ 从大到小排序
这样在处理上一次询问之后,下一次询问中$\le d$的询问中的点就全部被标记过了
我们求出这棵树的先序遍历(就是$dfs$序),假设 $i$ 节点左右在 $dfs$ 序出现的位置是 $l_i , r_i$。那么 $x$ 为根的树就转换成了$l_x ,r_x$之间的权值和。
这样我们将树抽象成区间
我们只需要维护单点修改(添加),查询区间和 这两种操作即可。
直接上线段树
代码 $O(n)$
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 2 * N;
int T;
int n, m;
int depth[N];
vector<int> dep[N]; // 每个深度的节点
int L[N], R[N], tot; // 每棵树的子树dfs范围
int e[M], ne[M], idx, h[N];
int ans[N], cnt;
struct Node
{
int l, r, v;
} tr[N * 8];
struct Query
{
int id, d, x;
} q[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int fa)
{
L[u] = ++tot;
dep[depth[u]].push_back(u);
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa)
continue;
depth[j] = depth[u] + 1;
dfs(j, u);
}
R[u] = tot;
}
void pushup(int u)
{
tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l == r)
return;
else
{
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
}
void modify(int u, int x)
{
if (tr[u].l == x && tr[u].r == x)
tr[u].v++;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid)
modify(u << 1, x);
else
modify(u << 1 | 1, x);
pushup(u);
}
}
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
return tr[u].v;
int res = 0;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid)
res += query(u << 1, l, r);
if (r > mid)
res += query(u << 1 | 1, l, r);
return res;
}
void solve()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
add(u, v), add(v, u);
}
depth[1] = 1;
dfs(1, -1);
build(1, 1, tot);
int last_dep = n + 1;
while (m--)
{
int op, x;
cin >> op >> x;
if (op == 1)
last_dep = x;
else
q[++cnt] = {cnt, last_dep, x};
}
sort(q + 1, q + 1 + cnt, [&](Query a, Query b)
{ return a.d > b.d; });
int l = n;
for (int i = 1; i <= cnt; i++)
{
while (l >= q[i].d)
{
for (int u : dep[l])
modify(1, L[u]);
l--;
}
ans[q[i].id] = query(1, L[q[i].x], R[q[i].x]);
}
for (int i = 1; i <= cnt; i++)
cout << ans[i] << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cin >> T;
T = 1;
while (T--)
{
solve();
}
return 0;
}