Codeforces Round #316 (Div. 2) D Tree Requests

Tree Requests

判断 \(V_i\) 的子树中，深度为 \(h_i\) 的结点上所带有的字符，能否组成一个回文串

启发式合并

维护所有深度上不同字符的数量，并且维护其奇数字符出现的次数

如果若干个字符能组成一个回文串，必然有：

• 偶数个字符，且不出现奇数次数的字符

• 奇数个字符，只能出现一个奇数次数的字符

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define pii pair<int, int>
typedef long long ll;
const int maxn = 1e5 + 10;
vector<int>gra[maxn];
int col[maxn], cnt[maxn], fa[maxn];
int siz[maxn], hson[maxn], ans[maxn];
int L[maxn], R[maxn], tp = 0, rnk[maxn];
int sum[maxn];
vector<pii>qs[maxn];

void dfs1(int now, int pre)
{
    L[now] = ++tp;
    fa[now] = pre;
    siz[now] = 1;
    hson[now] = -1;
    rnk[tp] = now;
    for(int nex : gra[now])
    {
        if(nex == pre) continue;
        dfs1(nex, now);
        siz[now] += siz[nex];
        if(hson[now] == -1 || siz[nex] > siz[hson[now]])
            hson[now] = nex;
    }
    R[now] = tp;
}

inline void add(int now)
{
    cnt[col[now]]++;
    sum[cnt[col[now]]]++;
}

inline void del(int now)
{
    sum[cnt[col[now]]]--;
    cnt[col[now]]--;
}

void dfs2(int now, bool keep)
{
    for(int nex : gra[now])
        if(nex != fa[now] && nex != hson[now]) dfs2(nex, false);
    if(hson[now] != -1) dfs2(hson[now], true);
    for(int nex : gra[now])
    {
        if(nex == fa[now] || nex == hson[now]) continue;
        for(int i=L[nex]; i<=R[nex]; i++)
            add(rnk[i]);
    }
    add(now);
    for(auto [k, id] : qs[now])
        ans[id] = sum[k];
    if(!keep)
    {
        for(int i=L[now]; i<=R[now]; i++)
            del(rnk[i]);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> col[i];
    for(int i=1; i<n; i++)
    {
        int a, b;
        cin >> a >> b;
        gra[a].push_back(b);
        gra[b].push_back(a);
    }
    for(int i=0; i<m; i++)
    {
        int a, b;
        cin >> a >> b;
        qs[a].push_back({b, i});
    }
    dfs1(1, 1);
    dfs2(1, true);
    for(int i=0; i<m; i++)
        cout << ans[i] << "\n";
    return 0;
}