Codeforces 570D Tree Requests

dsu on tree

題意

給一棵樹，每個節點有一個字母。一些查詢Q(x,d)，查詢x及其子樹中，與根節點距離為d的所有字母是否可以構成回文串。

思路

兩種思路，dfs序+樹狀數組或dsu on tree。

dfs序+樹狀數組

我們可以跑一遍dfs序，這樣子樹在dfs序中連續。dfs時同時處理出距根所有距離的節點。然後離線詢問，按深度排序，開26個樹狀數組。處理到每一層時将目前層所有節點加入對應字母的樹狀數組，然後對每個詢問的x的dfs序區間進行查詢。

複雜度 O(nlog2n) ，cf跑了1400ms，空間102400kb。

dsu on tree

标準dsu on tree闆子，每一個深度開個bitset記錄字母出現情況，第一次dfs記錄深度，第二次dfs更新對應深度的bitset，再做查詢。

複雜度 O(nlogn) ，cf跑了1000ms，空間59100kb。優秀啊~

代碼

dfs序+樹狀數組

#include<bits\stdc++.h>
#define M(a,b) memset(a,b,sizeof(a))
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const int MAXN=;
typedef long long LL;
struct Edge
{
    int to, ne;
}e[MAXN];
int head[MAXN], edgenum;
int val[MAXN];char c[MAXN];
int depth[MAXN];

struct Query
{
    int id;
    int u, dp;
}q[MAXN];
int res[MAXN];
bool cmp(Query a, Query b)
{
    return a.dp<b.dp;
}

int dfscount, in[MAXN], ou[MAXN];
int bit[][MAXN];
vector<int> dp[MAXN];
inline int lowbit(int i) { return i&(-i); }
void change(int i,int pos, int v)
{
    while(pos<MAXN)
        bit[i][pos]+=v, pos+=lowbit(pos);
}
int query(int i, int pos)
{
    int ans=;
    while(pos>)
        ans+=bit[i][pos], pos-=lowbit(pos);
    return ans;
}
void dfs(int u, int fa)
{
    in[u]=++dfscount;
    if(fa==-) depth[u]=;
    else depth[u]=depth[fa]+;
    dp[depth[u]].push_back(u);
    for(int i=head[u];~i;i=e[i].ne)
        dfs(e[i].to, u);
    ou[u]=dfscount;
}
int main()
{
    int n;
    while(scanf("%d", &n)==)
    {
        int qam;scanf("%d", &qam);
        M(head, -);edgenum=dfscount=;
        for(int i=;i<=n;i++)
        {
            int fa;scanf("%d", &fa);
            e[edgenum].to=i, e[edgenum].ne=head[fa], head[fa]=edgenum++;
        }
        scanf("%s", c+);
        for(int i=;i<=n;i++)
            val[i]=c[i]-'a';
        for(int i=;i<=qam;i++)
        {
            int t1, t2;scanf("%d%d", &t1, &t2);
            q[i].id=i;q[i].u=t1, q[i].dp=t2;
        }
        dfs(, -);
        sort(q+, q+qam+, cmp);
        int cnt=;
        for(int i=;i<=n;i++)
        {
            for(int j : dp[i])
            {
                int c=val[j];
                change(c, in[j], );
            }
            while(q[cnt].dp==i)
            {
                int x=in[q[cnt].u]-, y=ou[q[cnt].u];
                int tmp=;
                for(int k=;k<;k++)
                {
                    tmp+=((query(k, y)-query(k, x))%);
                }

                res[q[cnt].id]=(tmp<=);
                cnt++;
            }
            for(int j : dp[i])
            {
                int c=val[j];
                change(c, in[j], -);
            }
        }
        for(int i=;i<=qam;i++)
            if(res[i]) printf("Yes\n");
            else printf("No\n");
    }
    //system("pause");
    return ;
}
           

dsu on tree

#include<bits\stdc++.h>
#define M(a,b) memset(a,b,sizeof(a))
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const int MAXN=;
typedef long long LL;
struct Edge
{
    int to, ne;
}e[MAXN];
int head[MAXN], edgenum;
int val[MAXN];char c[MAXN];
int depth[MAXN], sz[MAXN], hson[MAXN];
void dfs(int u, int fa)
{
    if(fa==-) depth[u]=;
    else depth[u]=depth[fa]+;
    sz[u]=;
    for(int i=head[u];~i;i=e[i].ne)
    {
        int to=e[i].to;
        dfs(to, u);
        if(!hson[to]) hson[u]=to;
        else if(sz[hson[u]]<sz[to]) hson[u]=to;
        sz[u]+=sz[to];
    }
}
struct Query
{
    int id;
    int u, dp;
    int ne;
}q[MAXN];
int qhead[MAXN], res[MAXN];

int hs;
bitset<26> cnt[MAXN];
void suan(int u, int fa)
{
    cnt[depth[u]].flip(val[u]);
    for(int i=head[u];~i;i=e[i].ne)
        if(e[i].to!=hs)
            suan(e[i].to, fa);
}
void dfs(int u, int fa, int kep)
{
    for(int i=head[u];~i;i=e[i].ne)
        if(e[i].to!=hson[u])
            dfs(e[i].to, u, );

    if(hson[u]) dfs(hson[u], u, ), hs=hson[u];
    suan(u, fa);hs=;
    for(int i=qhead[u];~i;i=q[i].ne)
    {
        res[q[i].id]=(cnt[q[i].dp].count()<=);
    }
    if(!kep) suan(u, fa);
}

int main()
{
    int n;
    while(scanf("%d", &n)==)
    {
        int qam;scanf("%d", &qam);
        M(head, -);edgenum=;M(qhead, -);
        for(int i=;i<=n;i++)
        {
            int fa;scanf("%d", &fa);
            e[edgenum].to=i, e[edgenum].ne=head[fa], head[fa]=edgenum++;
        }
        scanf("%s", c+);
        for(int i=;i<=n;i++)
            val[i]=c[i]-'a';
        for(int i=;i<=qam;i++)
        {
            int t1, t2;scanf("%d%d", &t1, &t2);
            q[i].id=i;q[i].u=t1, q[i].dp=t2, q[i].ne=qhead[t1];qhead[t1]=i;
        }
        dfs(, -);
        dfs(, -, );

        for(int i=;i<=qam;i++)
            if(res[i]) printf("Yes\n");
            else printf("No\n");
    }
    //system("pause");
    return ;
}