题目大意

你有一棵有 $n$ 个节点的有根（根为 $1$ ）树，你要对对其进行 $m$ 次操作。

每次操作给出两个数 $a_i, b_i$，你要往以 $a_i, b_i$ 为根的子树内每个点的集合里加入数 $i$。

问最后对于每个点有多少个点（不包括自己）的集合与其交集非空。

$1 \leq n, m \leq 10^5$

题目大意

给定一颗有根树，根为 $1$ ，有以下两种操作：

1. 标记操作：对某个结点打上标记。（在最开始，只有结点 $1$ 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）

2. 询问操作：询问某个结点最近的一个打了标记的祖先。（这个结点本身也算自己的祖先）

$1 \leq n, q \leq 10^5 $

题目大意

有一棵$n$个节点的树，点有点权，对于每个节点，你要求出离这个节点距离$k$以内的节点的点权和

$1 \leq n \leq 10^5, 1 \leq k \leq 20$

可以发现题目可以转化为把从$l$到$r$节点到$1$的路径上的点的点权都加上$1$，然后统计$1$到$z$路径上的点权

然后发现这个东西可以差分。。。

于是我们就把询问拆成$l-1$和$r$,然后按$r$排序

从$1$到$n$把$1$到$i$路径点权全部$+1$

询问时查询$1$到$z$路径点权和

很明显这是一道树剖题

但是，树剖是在点上进行的操作，如何把它转化到边上呢？

不难发现，每一个点与他的父亲节点之间仅有唯一的一条边

于是我们可以把这条边的边权转化为这个儿子节点的点权。

就是个树剖的模板题嘛。。。。

zcy会写树剖啦！

经典的DFS序入门题

一道经典的DFS序入门题.

本题考察选手对DFS及树结构的掌握程度