【算法】dsu on tree初探

　　dsu on tree的本质是树上的启发式合并，它利用启发式合并的思想，可以将O(N^2)的暴力优化成O(NlogN)，用于不带修改的子树信息查询。

　　具体如何实现呢？对于一个节点，继承它重儿子的信息，轻儿子直接dfs统计，更新完本节点的答案后，再dfs一次清除轻儿子的信息，相当于一个启发式合并的过程，因为一次合并会使得被遍历的子树变大一倍，所以一棵子树最多遍历logn次，也就是一个点最多被遍历logn次，于是最劣复杂度为O(NlogN)。

　　dsu on tree的具体流程

　　　　dfs计算轻儿子的答案，（有时候也需要继承轻儿子的答案）

　　　　dfs计算重儿子的答案，继承重儿子的答案（有时候不需要）

　　　　dfs计算轻儿子的贡献

　　　　更新当前结点的答案

　　　　dfs删去轻儿子的贡献

模板代码：

void dfs1(int x)

{

    size[x]=;

    for(int i=last[x];i;i=e[i].pre)

    dfs1(e[i].too),size[x]+=size[e[i].too],size[e[i].too]>size[son[x]]&&(son[x]=e[i].too);

}

void update(int x,int fa,int delta)

{

//    更新信息

    for(int i=last[x];i;i=e[i].pre)

    if(e[i].too!=fa&&e[i].too!=skip)update(e[i].too,x,delta);

}

void dfs2(int x,int fa,bool heavy)

{

    for(int i=last[x];i;i=e[i].pre)

    if(e[i].too!=fa&&e[i].too!=son[x])dfs2(e[i].too,x,);

    if(son[x])dfs(son[x],x,),skip=son[x],ans[x]=ans[son[x]];//有时不需要继承

    update(x,fa,);skip=;

    ans[x]+=....//有时在update里更新答案

    if(!heavy)update(x,fa,-);

}

　　例1 CF600E

　　题目大意：统计每一个子树里众数的和（可以有多个众数）

　　记录每种颜色的出现次数，然后就是模板题了...

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int too,pre;}e[maxn];

int n,x,y,tot,zs,skip;

int last[maxn],col[maxn],cnt[maxn],son[maxn],size[maxn];

ll sum,ans[maxn];

inline void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

inline void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}

void dfs1(int x,int fa)

{

    size[x]=;

    for(int i=last[x],too;i;i=e[i].pre)if((too=e[i].too)!=fa)

    dfs1(too,x),size[x]+=size[too],size[too]>size[son[x]]&&(son[x]=too);

}

void update(int x,int fa,int delta)

{

    cnt[col[x]]+=delta;

    if(delta>&&cnt[col[x]]>zs)zs=cnt[col[x]],sum=col[x];

    else if(delta>&&cnt[col[x]]==zs)sum+=col[x];

    for(int i=last[x];i;i=e[i].pre)

    if(e[i].too!=fa&&e[i].too!=skip)

    update(e[i].too,x,delta);

}

void dfs(int x,int fa,bool heavy)

{

    for(int i=last[x];i;i=e[i].pre)

    if(e[i].too!=fa&&e[i].too!=son[x])dfs(e[i].too,x,);

    if(son[x])dfs(son[x],x,),skip=son[x];

    update(x,fa,);ans[x]=sum;skip=;

    if(!heavy)update(x,fa,-),zs=sum=;

}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(col[i]);

    for(int i=;i<n;i++)read(x),read(y),add(x,y),add(y,x);

    dfs1(,);dfs(,,);

    for(int i=;i<=n;i++)printf("%lld ",ans[i]);

}

　　例2 CF741D

　　题目大意：每一条边有一个字符，求每一个子树里最长的路径使得路径上的字符经过重新排列可以成为回文串

　　这题有点像上场atcoder的D题...因为一个字符串经过重新排列可以成为回文串当且仅当每种颜色的出现次数为偶数或者只有一种颜色的出现次数为奇数，于是可以想到利用异或来判断。将每一种字符映射到二进制上的一位(1<<(ch-'a))，预处理出点到根节点的路径上的异或值，那么判断两个节点的路径上是否可以经过重新排列成为回文串就是st[x]^st[y]是不是0或者2的幂。

　　所以这题我们只需要记录状态为i的最深深度，然后就又是模板题了。

　　注意状态为i的如果没有要设为-inf，否则会GG （调了一天T T

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int maxn=,inf=1e9;

struct poi{int too,dis,pre;}e[maxn];

int n,x,y,tot,skip,sum;

int st[maxn],col[maxn],size[maxn],dep[maxn],son[maxn],mx[<<],last[maxn],ans[maxn];

char ch[];

inline void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

inline void add(int x,int y,int z){e[++tot].too=y; e[tot].dis=z; e[tot].pre=last[x]; last[x]=tot;}

void dfs1(int x,int fa)

{

    size[x]=;

    for(int i=last[x],too;i;i=e[i].pre) if((too=e[i].too)!=fa)

    {

        dep[too]=dep[x]+;

        st[too]=st[x]^(<<e[i].dis);

        dfs1(too,x);

        size[x]+=size[too];

        if(size[too]>size[son[x]]) son[x]=too;

    }

}

void Count(int x,int fa,int f)

{

    sum=max(sum,mx[st[x]]+dep[x]-*dep[f]);

    for(int i=;i<;i++) sum=max(sum, mx[st[x]^(<<i)]+dep[x]-*dep[f]);

    if(x==f)return;

    for(int i=last[x],too;i;i=e[i].pre)

        if((too=e[i].too)!=fa && too!=skip) Count(too,x,f);

}

void update(int x,int fa,int delta)

{

    if(delta>) mx[st[x]]=max(mx[st[x]],dep[x]);

        else mx[st[x]]=-inf;

    for(int i=last[x],too;i;i=e[i].pre)

        if((too=e[i].too)!=fa && too!=skip) update(too,x,delta);

}

void dfs2(int x,int fa,bool heavy)

{

    for(int i=last[x],too;i;i=e[i].pre)

        if((too=e[i].too)!=fa && too!=son[x])

            dfs2(too,x,), ans[x]=max(ans[x],ans[too]);

    if(son[x]) dfs2(son[x],x,), skip=son[x], ans[x]=max(ans[x],ans[son[x]]);

       sum=; Count(x,fa,x); mx[st[x]]=max(mx[st[x]],dep[x]);

    for(int i=last[x],too;i;i=e[i].pre)

        if((too=e[i].too)!=fa && too!=skip)

            Count(too,x,x), update(too,x,);

    ans[x]=max(ans[x],sum); skip=;

    if(!heavy) update(x,fa,-);

}

int main()

{

    read(n); for(int i=;i<(<<);i++) mx[i]=-inf;

    for(int i=;i<=n;i++) read(x), scanf("%s",ch), y=ch[]-'a',add(x,i,y);

    dfs1(,); dfs2(,,);

    for(int i=;i<=n;i++) printf("%d ",ans[i]);

}

　　例3 NOIP模拟赛10.23 T2

巴特西

【算法】dsu on tree初探

最新文章

热门文章