CF741 D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

题目意思很清楚了吧，那么我们从重排回文串的性质入手。

很容易得出，只要所有字符出现的次数都为偶数，或者有且只有一个字符出现为奇数就满足要求了。

然后想到什么，Hash？大可不必，可以发现字符\(\in [a,v]\)，一共\(22\)种，那么我们套路的状压一下即可。

题目放在一棵树上，我们不禁联想树上常用的算法——倍增，树剖，树分治，树上莫队，LCT，但是好像都不好做。

注意到这是一个静态子树信息维护，所以我们可以用一个比较冷门的算法Dsu on Tree（中文名叫树上启发式合并）

它的大体思路很简单，就是对暴力DFS的过程做了优化。先类似于轻重剖分那样求出轻重儿子，然后每次先暴力递归轻儿子，算完贡献然后删去。

然后再统计重儿子的贡献，做完不再删去，然后最后回溯的时候把轻儿子的再加回去。

由于每跳一次重儿子，子树规模至少减少一半，所以每一个节点最多向上合并\(\log n\)次，所以总复杂度是\(O(n\log n)\)的。

再来考虑这个问题，由于异或以及深度的可减性所以我们可以开一个数组统计子树内每种状态的最大深度，每次根据这个数组更新信息即可。

不过要注意这样做的答案是强制过当前根节点的，不过由于这是个最值问题，我们可以把子树的信息向上取\(\max\)。

虽然会有一个\(22\)的常数，但是你要坚信CF神机是可以跑过去的。

总复杂度\(O(22n\log n)\)，常数很小。

CODE

#include<cstdio>

#include<cctype>

#define RI register int

#define CI const int&

#define Tp template <typename T>

#define add(x,y) e[++cnt]=(edge){y,head[x]},head[x]=cnt

using namespace std;

const int N=500005,R=22,status=(1<<R)-1,INF=1e9;

struct edge

{

    int to,nxt;

}e[N]; int fa[N],n,head[N],cnt,dep[N],prefix[N],son[N],ans[N],size[N],bit[R+5],f[(1<<R)+5]; char ch;

class FileInputOutput

{

    private:

        static const int S=1<<21;

        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)

        #define pc(ch) (Ftop<S?Fout[Ftop++]=ch:(fwrite(Fout,1,S,stdout),Fout[(Ftop=0)++]=ch))

        char Fin[S],Fout[S],*A,*B; int Ftop,pt[15];

    public:

        Tp inline void read(T& x)

        {

            x=0; char ch; while (!isdigit(ch=tc()));

            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));

        }

        Tp inline void write(T x)

        {

        	if (!x) return (void)(pc('0'),pc(' ')); RI ptop=0;

        	while (x) pt[++ptop]=x%10,x/=10; while (ptop) pc(pt[ptop--]+48); pc(' ');

        }

        inline void get_alpha(char& ch)

        {

        	while (!isalpha(ch=tc()));

        }

        inline void Fend(void)

        {

        	fwrite(Fout,1,Ftop,stdout);

        }

        #undef tc

        #undef pc

}F;

inline void maxer(int& x,CI y)

{

    if (y>x) x=y;

}

#define to e[i].to

inline void DFS1(CI now)

{

    size[now]=1; for (RI i=head[now];i;i=e[i].nxt)

    {

        dep[to]=dep[now]+1; prefix[to]^=prefix[now]; DFS1(to);

        size[now]+=size[to]; if (size[to]>size[son[now]]) son[now]=to;

    }

}

inline void calc(CI now,CI par)

{

    RI i; for (i=0;i<=R;++i) maxer(ans[par],dep[now]+f[prefix[now]^bit[i]]);

    for (i=head[now];i;i=e[i].nxt) calc(to,par);

}

inline void Add(CI now)

{

    maxer(f[prefix[now]],dep[now]); for (RI i=head[now];i;i=e[i].nxt) Add(to);

}

inline void Del(CI now)

{

    f[prefix[now]]=-INF; for (RI i=head[now];i;i=e[i].nxt) Del(to);

}

inline void DFS2(CI now)

{

    RI i; for (i=head[now];i;i=e[i].nxt) if (to!=son[now])

    DFS2(to),Del(to); if (son[now]) DFS2(son[now]);

    maxer(f[prefix[now]],dep[now]); for (i=0;i<=R;++i)

    maxer(ans[now],dep[now]+f[prefix[now]^bit[i]]);

    for (i=head[now];i;i=e[i].nxt) if (to!=son[now]) calc(to,now),Add(to);

}

#undef to

int main()

{

    //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);

    RI i; for (F.read(n),i=2;i<=n;++i) F.read(fa[i]),F.get_alpha(ch),

    add(fa[i],i),prefix[i]=1<<ch-'a'; for (i=0;i<=status;++i)

    f[i]=-INF; for (i=0;i<R;++i) bit[i]=1<<i;

    for (DFS1(1),DFS2(1),i=1;i<=n;++i) ans[i]-=2*dep[i];

    for (i=n;i;--i) maxer(ans[fa[i]],ans[i]); for (i=1;i<=n;++i)

    F.write(ans[i]); return F.Fend(),0;

}

巴特西

CF741 D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

最新文章

热门文章