前言

一次模拟赛的传送门

只会的我就了,并且对于题解提供的的做法一脸懵逼。

看网上的其他大佬写的笔记,我自己画图看了一天才看懂(我太蒻了),于是就有了这篇学习笔记。

概念篇/基础运用

算法简介

现在考虑这样一类树上统计问题:

  • 无修改操作,询问允许离线

  • 对子树信息进行统计(链上的信息在某些条件下也可以统计)

树上莫队?点分治?

可以把它们吊起来打!

运用树剖中的轻重链剖分,将轻边子树信息累加到重链上进行统计,拥有的优秀复杂度,常数还贼TM小,你值得拥有!

//虽说是dsu on tree,但某个毒瘤@noip说这是静态链分治

//还有其他的数据结构神du仙liu说它可以被看成是静态的树剖(因为其在树上有强大的统计信息的能力,但不能支持修改操作),与正常的树链剖分相对

//所以我同时保留这几种说法,希望数据结构神du仙liu们不要喷我这个juruo

算法实现

  • 遍历所有轻儿子,递归结束时消除它们的贡献

  • 遍历所有重儿子,保留它的贡献

  • 再计算当前子树中所有轻子树的贡献

  • 更新答案

  • 如果当前点是轻儿子,消除当前子树的贡献


那么这里有人可能就要问了,为什么不保留求出的所有答案呢?这样复杂度就更优了啊

如果这样的话,当你处理完一颗子树的信息时,再递归去求解另一颗子树时,

已有的答案就会与当前子树信息相混淆,就会产生错误答案。


所以,从这我们看出,一个节点只能选择一个子节点来保留答案

其它的都要去暴力求解

那么选择哪一个节点能使复杂度最优呢?

显然,我们要尽量均衡答案被保留的子树和不被保存的子树的大小

这是不是就很像树链剖分划分轻重儿子了呢?

人工图解

因为窝太蒻了一开始没怎么理解它,所以有了图解这个环节23333。

  • 比如现在有一个已经剖好的树(粗边为重边,带红点的是重儿子):

  • 首先,我们先一直跳轻儿子跳到这个位置:

  • 记录它的答案,并撤销影响,一直往轻儿子上跳

  • 然后发现下一步只能跳到一个重儿子上,就记录他的答案并保存(下文图中被染色的点即为目前保存了答案的点)

  • 接着回溯到父节点上,往下计算答案

  • 因为重儿子保存了答案被标记,往下暴力计算的时候只会经过轻边及轻儿子(即这条边和号节点)

  • 同理,号点也可进行类似操作,因为它的重儿子号节点已保存了这颗子树的答案,只需上传即可,

    不用再从这个位置再往下走统计答案,唯一会暴力统计答案的只有它的轻儿子号节点

  • 然后继续处理根节点另一个轻儿子,一直到叶子节点收集信息

  • 最后,对根节点的重儿子进行统计,如图,先对箭头所指的两个轻儿子进行计算

  • 接着对每一个重儿子不断保存答案,对轻儿子则暴力统计信息,将答案不断上传

  • 然后,对于根节点的处理同上即可

大致代码:

inline void calc(int x,int fa,int val)
{
    ......................
    /*
        针对不同的问题
        采取各种操作
    */
    for(rg int i=0;i<(int)G[x].size();++i)
    {
        int v=G[x][i];
        if(vis[v] || v==fa) continue;
        calc(v,x,val);
    }
}
inline void dfs(int x,int fa,int keep)//keep表示当前是否为重儿子
{
    for(int i=0;i<(int)G[x].size();++i)
    {
        int v=G[x][i].v;
        if(v==fa || v==son[x]) continue;
        dfs(v,x,0);
    }
    if(son[x]) dfs(son[x],x,1),vis[son[x]]=true;//标记重儿子
    calc(x,fa,1);vis[son[x]]=false;//计算贡献
    ans[x]=....;//记录答案
    if(!keep) calc(x,fa,-1);//不是重儿子,撤销其影响
}

如果是维护路径上的信息,大概还可以这么写:(如果有错,请大佬指出)

ps:关于对路径上信息进行维护的精彩应用,可以看最后道例题

inline void dfs(int x,int fa)
{
    siz[x]=1,dep[x]=dep[fa]+1,nid[rev[x]=++idx]=x;
    //再次借助树剖的思想,子树内节点顺序转为线性 
    for(rg int i=0;i<(int)G[x].size();++i)
    {
        int v=G[x][i].v,w=G[x][i].w;
        if(v==fa) continue;
        dfs(v,x),siz[x]+=siz[v];
        if(!son[x] || siz[v]>siz[son[x]]) son[x]=v;
    }
}
inline void calc(int x,int val)
{//对x这一节点进行单独处理 
    if(val>0) //计算贡献 
    else //撤销影响 
}
inline void dfs2(int x,int fa,int keep)
{
    for(rg int i=0;i<(int)G[x].size();++i)
    {
        int v=G[x][i].v;
        if(v==fa || v==son[x]) continue;
        dfs2(v,x,0);
    }
    if(son[x]) dfs2(son[x],x,1);
    for(rg int i=0;i<(int)G[x].size();++i)
    {
        int v=G[x][i].v;
        if(v==fa || v==son[x]) continue;
        for(rg int j=0;j<siz[v];++j)
        {
            int vv=nid[rev[v]+j]; 
            ..........
            //更新答案 
        }
        for(rg int j=0;j<siz[v];++j) calc(nid[rev[v]+j],1);
    }
    calc(x,1);
    ..........//更新答案 
    if(!keep) for(rg int i=0;i<siz[x];++i) calc(nid[rev[x]+i],-1);
}

复杂度证明

不感兴趣的大佬可以跳过这一段。(蒟蒻自己乱的证明,如果有错请大佬指出)

  • 显然,根据上面的图解,一个点只有在它到根节点的路径上遇到一条轻边的时候,自己的信息才会被祖先节点暴力统计一遍

  • 而根据树剖相关理论,每个点到根的路径上有条轻边和条重链

  • 即一个点的信息只会上传

  • 如果一个点的信息修改是的,那么总复杂度就是

几道可爱的例题

例题:[](https://www.luogu.org/problem/U41492)

此题来自[洛咕日报第篇](https://www.luogu.org/blog/codesonic/dsu-on-tree)作者[](https://www.luogu.org/space/show?uid=45443)。


  • 我们可以维护一个全局数组,代表正在被计算的子树的每种颜色的数量

  • 每次计算子树贡献的时候,把节点信息往里面加就行了,如果一个颜色第一次出现,则颜色种类数

  • 对于需要撤销影响的子树,把信息从里面丢出来即可,如果被删除的颜色只有这一个,则颜色种类数

例题:[](https://www.luogu.org/problem/CF600E)

公认模板题,相比于上题只是增加了对每种数量的颜色和的统计。

  • 我们可以维护数组,表示某个颜色出现的次数;再维护一个数组,表示当前子树出现了次的颜色的编号和

  • 对节点信息统计时,先把它在数组里的贡献删掉,更新了数组后再添回去

  • 然后别忘了开血的教训

应用篇/各种灵活运用

CF570D Tree Requests


窝太菜了,不会二进制优化,只会

  • 首先,因为要形成回文串、又可以对字符进行任意排列,所以最多只能有一种字母的出现次数为奇数

  • 然后我们维护一个数组,统计每个深度所有字母的出现次数:

cnt[dep[x]][s[x]-'a']+=val;
  • 最后再一下就好了

CF246E Blood Cousins Return


  • 首先用把给的所有名字哈希成的数字

  • 题目就可以转化为求出每个深度有多少不同的数

  • 同样,对每个深度开个去重并统计

  • 然后就是套板子的事情了

CF208E Blood Cousins


  • 显然原问题可以转化为求该点的级祖先有多少个级儿子(如果没有级祖先,答案就是0)

  • 而一个点级儿子即为在以为根节点的子树中有多少点的

  • 把所有询问读进来,求出相关的点的级祖先(可以离线处理,也可以倍增搞;如果时空限制比较紧,就采取前者吧)

  • 然后因为是统计节点数,所以开一个普通的数组维护即可。最后答案别忘了,因为算了自己

扔一个加强版的():[](https://www.luogu.org/problem/P5384)

友情提醒:上面这道良心题不仅卡空间,还卡时间(如果你用dsu on tree)

IOI2011 Race


点分治的题怎么能用点分治呢?而且这还是dsu on tree学习笔记

  • 首先,这道题是对链的信息进行统计,就不能再像对子树的统计方法去搞♂了,所以需要一些奇技淫巧

  • 思路与点分治一样,对于每个节点,统计经过的路径的信息

  • 注意到这道题链上的信息是可加减的,所以我们可以不保存的子孙的信息,而是保存每个节点到根节点的信息,在统计的时候在减去根节点的信息

  • 然后我们考虑如何统计,我们可以在每个节点维护一个桶,记录从这个点往下走的所有路径中,能形成的每种路径权值和以及其所需要的最少的边的数量:

  • 对于,计算出其到的距离及深度差(可以看成路径上的节点数),并用 k−dis来更新答案。

  • 然后用刚才得到的对应的来更新的值。

  • 这样就相当于,用每个的链,与之前桶中所保存某条链的路径权值和之和恰为的拼成一条路径,并更新答案。然后,再把它也加入桶中

  • 再套上的板子,每个节点保存它的重儿子的 桶的信息即可

虽然是的,但常数小,咱不慌

但是窝太菜了,用作桶不开个点(毕竟用了,还有两只),有空再重写一遍233

貌似用不开也卡得过去。。

NOIP2016 天天爱跑步


  • 首先,我们可以把这条路径拆成两段来考虑

  • 考虑在第一段路径上一点能观测到该玩家的条件是:

  • 同理,在第二段路径上一点能观测到该玩家的条件是:,即

  • 然后可以用差分的思想,对每个节点开两个桶进行统计

  • 中插入

  • 中插入

  • 因为会对都进行统计,所以在其中删除

  • 同理,在中删除

  • 然后用统计即可,答案为

注意到可能小于零,为了避免负数下标、又不想套,我们可以使用如下

int up[N],CNT[N<<1],*down=&CNT[N];
//把donw[0]指向CNT[N],这样就可以给负数和正数都分配大小为N的空间

跑的虽然没有普通的差分快,不过吊打线段树合并还是绰绰有余的

[Vani有约会]雨天的尾巴

跟天天爱跑步差不多,就不画图了(~懒)

  • 同上题,用差分的思想,对每个节点的增加和删除开两个桶统计

  • 同时,这题要维护每个点出现的最多物品的种类,直接开个线段树维护就好了

,常数应该和树剖差不多,不过因为每个点都要进行增加删除两个操作,常数大了一倍,而且还用了线段树,所以

不过依然比部分线段树合并跑的快2333

由以上三题,我们可以看出,在一定条件下,也是可以在链上搞♂事情的

比如满足链上信息可加减性,后两道题可以用差分将链上的修改/询问转化为点上的修改/询问

可以应用的条件肯定不止以上两种,因为窝太蒻了,只见识了这些题,以后看到其他类型的也会补上来

射手座之日


现在终于可以回过头来解决这个题了

留给大家思考吧,要代码的话可以私信我

虽然有很多大佬会线段树合并或虚树上秒切这道题,不过还是希望用

参考资料/总结

参考资料

总结

以后还会不定期地添加的相关题目~

如果有需要,我会把最后那道题的代码贴出来