树论

讲稿

by $\mathcal{QingJun}$

1. 题目描述一律放在引用里，简单的例题可能无标题无$\LaTeX$且solution也放在引用里。例子：
   

   （题目描述）这是一道简单的例题
   sol：！@#￥%%……

2. 题目太简单不要D我，太难也不要D我。
3. 稿子写得比较简单，大家要认真听。
4. 推荐一个图论作图工具 Graph Editor
5. 推荐一个编辑器 Typora
6. 推荐一个数学作图工具 GeoGebra

1. 轻工业

1.1 XX序

1. dfs序：仅在第一次访问 $u$ 时加入 $u$。
2. 括号序： 在第一次访问 $u$ 与结束访问 $u$ 时加入 $u$。
3. 欧拉序： 在第一次访问 $u$ 与每次回溯 $u$ 时都加入 $u$。

明显dfs序可以对应子树。

给定一棵n个节点的树，m次查询，每次查询需要求出某个节点深度为h的所有子节点。

1.2 维护权值和

维护权值和这个问题，有这么几种常见情况：
1. 单点修改子树询问
2. 子树修改单点询问
3. 子树修改子树询问
4. 链修改单点询问
5. 单点修改链询问
请大家自行思考怎么做

1.3 重链剖分

给定一棵带边权的树，要求支持两种操作：
1.修改某条边的权值
2.询问树中两点之间唯一路径上的最大边权。
sol：线段树维护最大值，完了。

当然，也有稍微复杂点的。

[SDOI2011]染色

给定一棵 $n$ 个节点的无根树，共有 $m$ 个操作，操作分为两种：

1. 将节点 $a$ 到节点 $b$ 的路径上的所有点（包括 $a$ 和 $b$）都染成颜色 $c$。
2. 询问节点 $a$ 到节点 $b$ 的路径上的颜色段数量。

颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成：11、222、1。

先解决序列问题，线段树维护颜色段数、左端颜色、右端颜色，合并随便讨论下。然后轻重链切换时注意也要合并。

2 树的直径与重心

2.1 树的直径

结论1： 离任意一个点最远的点一定是直径的一端。
这就导出第一种求法，两遍bfs。
第二种求法是dp，维护子树内最长链与次长链。
结论2： 两棵树合并后，新树的直径端点一定从原树直径端点中产生。

很多树论题一眼不会，可以从直径入手思考。

[APIO2010]巡逻

有一棵树，我们可以在树上加上 $k$ 条边，使从一号节点出发遍历每条边并最终回到一号节点经过的路径最短。
$k=1\text{或}2$

1. $k=0$
   $2*(n-1)$
2. $k=1$
   加入一条边会形成一个环，环上所有边都少走一次。直接连直径。
3. $k=2$
   可以扩展 $k=1$ 的结论，再找一个环。但是一条边最多少走一次，因此把第一次求出的直径边权赋为 $-1$ 再求一次直径即可。注意这次不能两遍bfs。

2.2 树的重心

$n$ 为奇数只有一个重心，$n$ 为偶数可能两个重心。

甩一波结论：

1. 删除重心后所得的所有子树，节点数不超过原树的1/2；
2. 树中所有节点到重心的距离之和最小，如果有两个重心，那么他们距离之和相等；
3. 两个树通过一条边合并，新的重心在原树两个重心的路径上；
4. 树删除或添加一个叶子节点，重心最多只移动一条边。

[CSP2019]树的重心

给出一棵树，我们知道，断掉一条边后，它会分成两棵子树，定义这条边的贡献为这两棵子树的重心的编号和。求所有边的贡献和。
$n\le 3*10^5$

考虑每个点的贡献。
先用整棵树的重心作根。
除了 $rt$ 以外点 $x$ ，断掉 $x$ 子树内的点显然不能使 $x$ 成为重心。
设 $s_x$ 为 $x$ 的子树大小，$g_x$ 为 $x$ 的重儿子的大小，$(u,v)$ 为断掉的边，$S$ 为 $(u,v)$ 另一棵（不包括 $x$ 那棵）子树的大小。

如图，$5$ 号点为 $x$，假设要断掉 $(2,3)$。
那么要使 $x$ 成为圆圈里面这棵子树的重心，要满足

1. $(u,v)$ 在 $x$ 的子树外。
2. $2g_x\le n-S$
3. $2(n-S-s_x)\le n-S$

先不管第一条，第二条和第三条合并为 $n-2s_x\le S \le n-2g_x$。
这个大致做法是用树状数组动态维护每个满足条件2.3.的 $S$ 的个数，询问就是区间查。
然后减掉在 $x$ 子树内的合法边，这个可以用类似天天爱跑步的做法，考虑进 $x$ 与出 $x$ 的变化值。

还要算出 $rt$ 的贡献。
设 $rt$ 的儿子中子树最大的节点为 $t1$，次大的节点为 $t2$。
若 $(u,v)$ 在 $t1$ 中，则需满足 $2s_{t2}\le n-S$。
若 $(u,v)$ 在 $t2$ 中，则需满足 $2s_{t1}\le n-S$。
可以顺便处理。

3 基环树

1. @$\color{Black}{\text{k}}\color{Red}{\text{oalawy}}$ 已经讲过了。
2. 我会的是 @$\color{Black}{\text{k}}\color{Red}{\text{oalawy}}$ 讲过的的子集。
3. 所以我不用讲了。

4 小清新例题

4.1 [HDU5156]

$n$ 节点树，根为 $1$，一个节点可能有多个不同颜色的苹果，但苹果总数为 $m$。任务是：对于每个节点，输出它的子树内有多少种颜色的苹果。
$n,m\le 10^5$

思路1

对每种颜色分开考虑贡献。对每个颜色搞个虚树，要做到虚树上每个点只贡献一次。

思路2

转线性问题，假设要询问 $[l,r]$ 中的颜色种数，求出 $pre_i$ 表示上一个与 $i$ 颜色相同的位置，那么

$$Ans_{[l,r]}=\sum_{l\le i \le r}[pre_i<l]$$
扩展到树上相当于询问 $n$ 个子树区间。这是个经典的二维数点问题，扫描线解决。

4.2 [NOIP2016]天天爱跑步

$n$ 个节点的树，有 $m$ 个玩家，第 $i$ 个玩家会在时刻 $0$ 出现在 $s_i$ 然后以每秒一条边的速度沿唯一路径跑到 $t_i$ ，然后瞬间消失。每个节点上有一个观察员，他会在 $w_i$ 时刻记录在 $i$ 号节点停留的玩家个数 $cnt_i$。求出 $cnt$ 数组。
$n,m\le 10^5$

玩家们都可以拆成从下到上的路径，比如一种情况下，$v$ 对 $u$ 有贡献当且仅当 $w_u=d_v-d_u \Leftrightarrow w_u+d_u=d_v$ 开个全局桶统计。具体地说，看进 $x$ 的子树，与出 $x$ 的子树时桶的差值。注意 lca 处可能会算重，要减去。

4.3 [CF280C] Game on Tree

给定一棵有根树，每次随机选一个未被删除的点，将以它为根的子树删除。
求删除整棵树所用的期望步数。
$n \le 10^5$

期望的线性性。
你可以理解成，总的期望等于每个点贡献期望的和。
一个点有贡献，即被作为根删除的概率是多少呢？$1/dep_u$。

所以说遇到期望题优先考虑一下期望的线性性，就像遇到位运算题优先按位考虑。

4.4 ？？？

给你一棵树，问距离为 $3$ 的倍数的无序点对有多少个。
$n \le 10^5$

如果淀粉质学傻了可能直接上点分了，但这题不需要。
$dp_{i,j}$ 表示以 $i$ 为根的子树中到 $i$ 距离 mod 3等于 $j$ 的点的个数。
合并点 $i$ 的儿子时，顺便统计当前儿子与前缀儿子组成的贡献。

4.5 [JZOJ5050]颜色树

$n$ 个点的树，每个点有一种颜色。一共有 $k$ 种颜色。求含 $k$ 种颜色的路径数量。
$n\le 5*10^4,k\le 10$
Ps:出题人特意卡了空间 禁用状压 DP

状压咋做？$\Theta(n2^{2k})$。FWT优化到 $\Theta(n2^k\log({2^k}))=\Theta(n2^kk)$。这咋过？？？
[JZOJ5050]颜色树 咋状压？
在座的能教教我吗。

正解大概是 $\Theta(n2^k)$ 的容斥做法。枚举不选颜色集合 $S$ ，删掉这些点，然后剩下一坨联通块，求出两端在不同联通块的路径数量。

4.6 [HDU4912]

$n$ 个节点的树，给出 $m$ 条路径 $(u_i,v_i)$，你需要选出尽量多的路径，要求路径之间没有公共点。
$n,m \le 10^5$

贪心，考虑从下往上贪心地选取
自底向上，对于lca在 $i$ 上的一条路径，如果可选，那么一定会选。
怎么判断是否可选？
若选取了lca为 $i$ 的一条路径，将整棵子树 $i$ 均标记，注意若发现一个点已标记即可返回。

4.7 [bzoj1117]救火站

给你一棵 $n$ 节点的树，现在要建立一些消防站，有以下要求:
1.消防站要建立在节点上，每个节点可能建立不只一个消防站。
2. 每个节点应该被一个消防站管理，这个消防站不一定建立在该节点上。
3. 每个消防站可以管理至多 $s$ 个节点。
4. 消防站只能管理距离（两点间最短路径的边数）不超过 $k$ 的结点。请问至少要设立多少个消防站。
$n\le 10^5,k\le 20$

我们的策略是，到万不得已时才放消防站。
设 $need[x][i]$ 表示 $x$ 的第 $i$ 层还有多少节点需要管理，$left[x][i]$ 表示 $x$ 的第 $i$ 层还余下多少控制力。

void dfs(int x,int f)
{
    fa[x]=f; need[x][0]=1;
    for(int i=head[x];i;i=e[i].next)
    {
        int to=e[i].to;
        if(to==fa[x]) continue;
        dfs(to,x);
        for(int j=1;j<=k;j++) need[x][j]+=need[to][j-1];
        for(int j=k-1;j>=0;j--) lef[x][j]+=lef[to][j+1];
    }
    ll tmp=(need[x][k]+s-1)/s;
    ans+=tmp;
    lef[x][k]+=(ll)tmp*s;
    for(int i=0;i<=k;i++)
    {
        if(lef[x][i])
        {
            for(int j=i;j>=0&&(j>=i-1||x==1);j--)
            {
                if(lef[x][i]<=need[x][j])
                {
                    need[x][j]-=lef[x][i];
                    lef[x][i]=0;
                    break;
                }
                lef[x][i]-=need[x][j];
                need[x][j]=0;
            }
        }
    }
}
int main(){
    ……
    dfs(1,0);
    for(int i=0;i<=k;i++) tot+=need[1][i];
    ans+=(tot+s-1)/s;
    ……
}

4.8 [CF735E]Ostap and Tree

问对一棵树染色,初始无色,要求距每个点最近的染色点的距离不超过 $k$ 的染色方法总和 $\bmod\text{ }10^9+7$。
$n\le 100,k\le \min(n-1,20)$

题解