M_sea

CF914E Palindromes in a Tree
CodeForcesLuogu分析点分治。显然,一条路径合法,当且仅当路劲上只有一个字母出现了奇数次。注意只有a~...
扫描右侧二维码阅读全文
24
2018/12

CF914E Palindromes in a Tree

CodeForces

Luogu

分析

点分治。

显然,一条路径合法,当且仅当路劲上只有一个字母出现了奇数次。

注意只有a~t,可以大力状压,便于判断。

一些要注意的地方写代码里了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=200010;

struct Edge { int v,nxt; };
Edge e[MAXN<<1];
int head[MAXN],cnt=0;
int n,root,sum;
int val[MAXN],vis[MAXN],sz[MAXN],f[MAXN],t[1<<21];
int ans[MAXN];

inline void addEdge(const int u,const int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

inline void getroot(const int u,const int fa) {
    sz[u]=1,f[u]=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v==fa||vis[v]) continue;
        getroot(v,u); sz[u]+=sz[v];
        f[u]=max(f[u],sz[v]);
    }
    f[u]=max(f[u],sum-sz[u]);
    if (f[u]<f[root]) root=u;
}

inline void Dfs(const int u,const int fa,const int w,int S) {
    t[S^=(1<<val[u])]+=w;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v!=fa&&!vis[v]) Dfs(v,u,w,S);
    }
}

inline int calc(const int u,const int fa,int S) {
    S^=(1<<val[u]); int num=t[S];
    for (re int i=0;i<20;++i) num+=t[S^(1<<i)];
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v!=fa&&!vis[v]) num+=calc(v,u,S);
    }
    ans[u]+=num; return num;
}

inline void solve(const int u) {
    vis[u]=1; Dfs(u,0,1,0);
    int num=t[0];
    for (re int i=0;i<20;++i) num+=t[1<<i];
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (vis[v]) continue;
        Dfs(v,u,-1,1<<val[u]);
        num+=calc(v,u,0);
        Dfs(v,u,1,1<<val[u]);
    }
    ans[u]+=num/2; //去重
    Dfs(u,0,-1,0);
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (vis[v]) continue;
        sum=sz[v],root=0;
        getroot(v,u);
        solve(root);
    }
}

char s[MAXN];

mainint main() {
    n=read();
    for (re int i=1,u,v;i<n;++i) {
        u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    scanf("%s",s+1);
    for (re int i=1;i<=n;++i) val[i]=s[i]-'a';
    sum=f[0]=n; getroot(1,0); solve(root);
    for (re int i=1;i<=n;++i) printf("%lld ",ans[i]+1); //一个节点也算
    putchar('\n');
    return 0;
}
最后修改:2019 年 05 月 26 日 03 : 47 PM

2 条评论

  1. xgzc

    %%%M_sea

    1. M_sea
      @xgzc

      您好fAKe啊qwq

发表评论