CF600E Lomsat gelral

Broken_Eclipse · 2022-08-12 21:21:16 · 个人记录

题意：

一棵树，每个节点有权值，求子树中权值次数最多的权值之和。

思路：

什么狗题，这就是dsu\ on\ tree吗。

我们发现如果每次查询子节点所代表的集合，时间复杂度将会达到难以让人接受的O(n^2)，所以我们就需要考虑减少时间开销。

发现每次递归查询完这些子节点，可以优先遍历所有轻儿子，然后再去找重儿子，只在找轻儿子的时候清空信息。因为最后一棵子树是不需要删除信息的（递归子树不删除信息会影响另一棵子树），这样能保证所有信息都能完整无误地存储而且大大降低了时间复杂度（最多只有logn条轻边）。

注意遍历和删除时都不要重复计算重儿子。

好难理解哼哼啊啊啊啊啊啊啊啊啊啊啊啊啊

代码：

inline void change(int u,int fa,int val,int p){
    nowc[stval[u]]+=val;
    if(nowc[stval[u]]>maxx){
        maxx=nowc[stval[u]];
        sum=stval[u];
    }else if(nowc[stval[u]]==maxx) sum+=stval[u];
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa||v==p) continue;
        change(v,u,val,p);
    }
}
inline void dfs(int u,int fa,int idx){
    for(Reg int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(fa==v||v==son[u]) continue;
        dfs(v,u,0);
    }
    if(son[u]) dfs(son[u],u,1);
    change(u,fa,1,son[u]);
    ans[u]=sum;
    if(!idx) change(u,fa,-1,0),sum=maxx=0;
    //统计子树信息时，不遍历重边，只遍历轻边
    //如该节点为重节点，那么信息全部保留
    //否则把轻边所有的信息清空
}