傳送門

CF
luogu（目前無法提交，詳見洛谷）
VJudge

題目大意

給定一顆以節(jié)點\(1\)為根的樹，包含\(n\)個節(jié)點，每個節(jié)點上都有一個字符\(c_i\)。
特別的，\(1\)號節(jié)點的深度為\(1\)。
共有\(m\)個問詢，每次詢問：在子樹\(v_i\)中所有深度（相對于根）\(h_i\)的所有節(jié)點能否構(gòu)成回文串。

數(shù)據(jù)范圍

• \(1\leq n,m\leq 5\times10^5\)
• \(1\leq v_i,h_i\leq n\)

樣例

輸入輸出樣例 #1

輸入 #1

6 5
1 1 1 3 3
zacccd
1 1
3 3
4 1
6 1
1 2

輸出 #1

Yes
No
Yes
Yes
Yes

思路

dsu on tree 板子題。
首先分析構(gòu)成回文串的要求，可以用一個cnt[dep][ch]數(shù)組統(tǒng)計當(dāng)前子樹中深度為\(dep\)的字符\(ch\)出現(xiàn)次數(shù)。
離線統(tǒng)計問詢中\(v_i=u\)的情況，在\(\text{dfs}\)到子樹\(u\)^[1]時只需將所有問詢?yōu)?span id="w0obha2h00" class="math inline">\(u,d_{u,j}\)對應(yīng)的cnt[d_u,j][0~25]全部&=1再加到\(res\)上，若最終\(res\leq 1\)則說明可以構(gòu)成回文串。

例

6 5
1 1 1 3 3
zacccd
1 1
3 3
4 1
6 1
1 2

中，將1 1和1 2掛到節(jié)點1上處理

dsu on tree

由于空間限制，必須重復(fù)利用cnt數(shù)組，為此，在每顆樹內(nèi)，除了最后一個被枚舉到的子樹不會影響到后續(xù)（根本就沒有后續(xù)）之外全部都要清空。
那么為什么需要清空子樹呢？
雖然某顆子樹不清空不會影響原樹的統(tǒng)計，但是會影響到原樹下的其他子樹（在其后枚舉的子樹）
為了子樹之間不影響，必須在dfs完時將其cnt清空。
在統(tǒng)計完最后一顆子樹時，就要統(tǒng)計原樹了。
那么很顯然如果將重子樹放在最后處理，清空的量是最少的。
雖然感覺很暴力玄學(xué)，但是時間復(fù)雜度仍然達(dá)到了驚人的\(\text{O(NlogN)}\)！
證明看這里
此時再把前面的子樹貢獻(xiàn)加回來，補(bǔ)全原樹。
最后特判根節(jié)點貢獻(xiàn)就行了。

代碼：

struct QUERY
{
	int id; // 此問詢在問詢列表中的位置
	int h;  // 此問詢的查詢深度
};
vector<QUERY> query[N]; // query[u]: 節(jié)點u的問詢
vector<int> e[N]; // 原題輸入給的是父親表示法，此處轉(zhuǎn)為兒子表示法
void merge(int u)
{
	++cnt[dep[u]][a[u]];
	for (auto j: e[u]) merge(j);
}
void delet(int u)
{
	--cnt[dep[u][a[u]]; // 或者直接等于0
	for (auto j: e[u]) delet(j);
}
// dfs1是樹剖，用于確定重兒子和深度
dfs2(int u, bool ishvy) // 當(dāng)前枚舉到子樹u，及是否為重兒子
{
	for (auto j: e[u]) { // 枚舉u的兒子
		if (j == hson[u]) continue;
		dfs2(j, 0);
	}
	// 注意判斷u是否為葉子節(jié)點，沒有重兒子
	if (hson[u]) dfs2(hson[u], 1);
	for (auto j: e[u]) {
		if (j == hson[u]) continue;
		merge(j);
	}
	++cnt[dep[u]][a[u]];
	int check = 0;
	for (auto i: query[u]) {
		for (int j = 0; j < 26; ++j) check += cnt[i.h][j] & 1;
		if (check <= 1) ans = 1;
	}
	if (!ishvy) delet(u);
}

坑

寫cnt的時候千萬不要將cnt[i][j]錯當(dāng)成子樹i了，我靈（腦）光（子）乍（抽）現(xiàn)（了）搞錯了結(jié)果過了樣例（好玄學(xué)？？？）然后WA了#TestPoint 2……

輸入的時候要警惕#TP41，輸入多打了一個回車，那些沒有使用以下代碼來跳過回車/空格

while (c == '\n || c == ' ') c = getchar();

的人估計就是這個點被HACK了
CF的hack機(jī)制還是太難繃了，居然有人用這種數(shù)據(jù)叉別人

完整代碼

/*
AUTHOR: peter_code
DATE: 25/08/08
PROBLEM: CF570D
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, a[N];   // 節(jié)點數(shù)、問詢數(shù)、節(jié)點權(quán)
vector<int> e[N]; // 節(jié)點i所有的兒子
int hson[N];      // 重兒子
int sz[N];        // 子樹大小
int dep[N];       // 節(jié)點深度
bool ans[N];      // 記錄"Yes"/"No"結(jié)果
int cnt[N][26];   // cnt[i][ch]: 深度為i，權(quán)為ch的節(jié)點出現(xiàn)次數(shù)

// 節(jié)點u上的問詢維護(hù)：
struct QUERY
{
    int id;       // 第 id 個問詢
    int h;        // 查詢樹中深度為h[i]的回文串構(gòu)成情況
};
vector<QUERY> query[N];

int dfs1(int u, int d)
{
    hson[u] = 0;
    sz[hson[u]] = 0;
    dep[u] = d;
    sz[u] = 1;
    for (auto i: e[u]) {
        sz[u] += dfs1(i, d + 1);
        if (sz[i] > sz[hson[u]]) hson[u] = i;
    }
    return sz[u];
}
void merge(int u) // 合并根為u的子樹
{
    ++cnt[dep[u]][a[u]];
    for (auto v: e[u]) merge(v);
}
void delet(int u) // 消除子樹u的貢獻(xiàn)
{
    cnt[dep[u]][a[u]] = 0;
    for (auto v: e[u]) delet(v);
}
void dfs2(int u, bool hvy) // 節(jié)點x，是否為重兒子（是否需保留信息）
{
    for (auto v: e[u]) {
        if (v == hson[u]) continue; // 優(yōu)先處理輕兒子，重兒子最后處理
        dfs2(v, 0);
    }

    // 統(tǒng)計u重兒子的貢獻(xiàn)（不會被清）
    if (hson[u]) dfs2(hson[u], 1); // 注意u為葉子節(jié)點無重兒子情況
    
    for (auto v: e[u]) {
        if (v == hson[u]) continue; // 重兒子已經(jīng)統(tǒng)計過了
        merge(v); // 統(tǒng)計輕兒子貢獻(xiàn)
    }
    ++cnt[dep[u]][a[u]]; // 特判根節(jié)點貢獻(xiàn)
    
    // 統(tǒng)計掛在節(jié)點u上的答案
    //printf("In Sub-tree %d:\n", u);
    for (auto i: query[u]) {
        int res = 0;
        for (int j = 0; j < 26; ++j) {
            //printf("\tThere are %d '%c' on depth %d.\n", cnt[u][i.h]);
            res += cnt[i.h][j] & 1;
        }
        ans[i.id] = res <= 1;
    }
    if (!hvy) delet(u);
}
int main()
{
    //freopen("D.in", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n; ++i) {
        int tmp;
        scanf("%d", &tmp);
        e[tmp].push_back(i);
    }
    char c = getchar();
    while (c == '\n' || c == ' ') c = getchar();
    for (int i = 1; i <= n; ++i) {
        a[i] = c - 'a';
        c = getchar();
    }
    for (int i = 1; i <= m; ++i) {
        int tmpx, tmpy;
        scanf("%d%d", &tmpx, &tmpy);
        query[tmpx].push_back({i, tmpy});
    }
    dfs1(1, 1);
    dfs2(1, 1);
    for (int i = 1; i <= m; ++i) {
        if (ans[i]) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

后記

本人第一次寫藍(lán)題題解，若有不滿，可在評論區(qū)提出，我一定盡力改正，謝謝！