Codeforces 570D TREE REQUESTS dfs序+树状数组

链接

题解链接:点击打开链接

题意:

给定n个点的树。m个询问

以下n-1个数给出每一个点的父节点,1是root

每一个点有一个字母

以下n个小写字母给出每一个点的字母。

以下m行给出询问:

询问形如 (u, deep) 问u点的子树中,距离根的深度为deep的全部点的字母是否能在随意排列后组成回文串,能输出Yes.

思路:dfs序,给点又一次标号,dfs进入u点的时间戳记为l[u], 离开的时间戳记为r[u], 这样对于某个点u,他的子树节点相应区间都在区间 [l[u], r[u]]内。

把距离根深度同样的点都存到vector里 D[i] 表示深度为i的全部点,在dfs时能够顺便求出。

把询问按深度排序,query[i]表示全部深度为i的询问。

接下来依照深度一层层处理。

对于第i层,把全部处于第i层的节点都更新到26个树状数组上。

然后处理询问,直接查询树状数组上有多少种字母是奇数个的。显然奇数个字母的种数要<=1

处理完第i层,就把树状数组逆向操作。相当于清空树状数组

注意的一个地方就是 询问的深度是随意的,也就是说可能超过实际树的深度,也可能比当前点的深度小。

所以须要初始化一下答案。。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <vector>
#include <string>
#include <time.h>
#include <math.h>
#include <iomanip>
#include <queue>
#include <stack>
#include <set>
#include <map>
const int inf = 1e9;
const double eps = 1e-8;
const double pi = acos(-1.0);
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if (c = getchar(), c == EOF) return 0;
while (c != '-' && (c<'0' || c>'9')) c = getchar();
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x < 0) { putchar('-'); x = -x; }
if (x > 9) pt(x / 10);
putchar(x % 10 + '0');
}
using namespace std;
const int N = 5e5 + 100;
typedef long long ll;
typedef pair<int, int> pii;
struct BIT {
int c[N], maxn;
void init(int n) { maxn = n; memset(c, 0, sizeof c); }
inline int Lowbit(int x) { return x&(-x); }
void change(int i, int x)//i点增量为x
{
while (i <= maxn)
{
c[i] += x;
i += Lowbit(i);
}
}
int sum(int x) {//区间求和 [1,x]
int ans = 0;
for (int i = x; i >= 1; i -= Lowbit(i))
ans += c[i];
return ans;
}
int query(int l, int r) {
return sum(r) + sum(l - 1);
}
}t[26];
int n, m;
char s[N];
vector<int>G[N], D[N];
int l[N], r[N], top;
vector<pii>query[N];
bool ans[N];
void dfs(int u, int fa, int dep) {
D[dep].push_back(u);
l[u] = ++top;
for (auto v : G[u])
if (v != fa)dfs(v, u, dep + 1);
r[u] = top;
}
int main() {
rd(n); rd(m);
fill(ans, ans + m + 10, 1);
for (int i = 0; i < 26; i++) t[i].init(n);
for (int i = 2, u; i <= n; i++)rd(u), G[u].push_back(i);
top = 0;
dfs(1, 1, 1);
scanf("%s", s + 1);
for (int i = 1, u, v; i <= m; i++) {
rd(u); rd(v); query[v].push_back(pii(u, i));
}
for (int i = 1; i <= n; i++)
{
if (D[i].size() == 0)break;
for (auto v : D[i]) t[s[v] - 'a'].change(l[v], 1); for (pii Q : query[i])
{
int ou = 0;
for (int j = 0; j < 26; j++)
{
if (t[j].query(l[Q.first], r[Q.first]))
ou += t[j].query(l[Q.first], r[Q.first]) & 1;
}
ans[Q.second] = ou <= 1;
}
for (auto v : D[i]) t[s[v] - 'a'].change(l[v], -1);
}
for (int i = 1; i <= m; i++)ans[i] ? puts("Yes") : puts("No"); return 0;
}
D. Tree Requests
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Roman planted a tree consisting of n vertices. Each vertex contains a lowercase English letter. Vertex 1 is
the root of the tree, each of the n - 1 remaining vertices has a parent in
the tree. Vertex is connected with its parent by an edge. The parent of vertex i is vertex pi,
the parent index is always less than the index of the vertex (i.e., pi < i).

The depth of the vertex is the number of nodes on the path from the root to v along
the edges. In particular, the depth of the root is equal to 1.

We say that vertex u is in the subtree of vertex v,
if we can get from u to v,
moving from the vertex to the parent. In particular, vertex v is in its subtree.

Roma gives you m queries, the i-th
of which consists of two numbers vihi.
Let's consider the vertices in the subtree vi located
at depthhi.
Determine whether you can use the letters written at these vertices to make a string that is a palindrome. The letters that are written in the vertexes, can be rearranged in any order to make
a palindrome, but all letters should be used.

Input

The first line contains two integers nm (1 ≤ n, m ≤ 500 000)
— the number of nodes in the tree and queries, respectively.

The following line contains n - 1 integers p2, p3, ..., pn —
the parents of vertices from the second to the n-th (1 ≤ pi < i).

The next line contains n lowercase English letters, the i-th
of these letters is written on vertex i.

Next m lines describe the queries, the i-th
line contains two numbers vihi (1 ≤ vi, hi ≤ n)
— the vertex and the depth that appear in thei-th query.

Output

Print m lines. In the i-th
line print "Yes" (without the quotes), if in the i-th
query you can make a palindrome from the letters written on the vertices, otherwise print "No" (without the quotes).

Sample test(s)
input
6 5
1 1 1 3 3
zacccd
1 1
3 3
4 1
6 1
1 2
output
Yes
No
Yes
Yes
Yes
Note

String s is a palindrome if reads the same from left to right and
from right to left. In particular, an empty string is a palindrome.

Clarification for the sample test.

In the first query there exists only a vertex 1 satisfying all the conditions, we can form a palindrome "z".

In the second query vertices 5 and 6 satisfy condititions, they contain letters "с" and "d"
respectively. It is impossible to form a palindrome of them.

In the third query there exist no vertices at depth 1 and in subtree of 4. We may form an empty palindrome.

In the fourth query there exist no vertices in subtree of 6 at depth 1. We may form an empty palindrome.

In the fifth query there vertices 2, 3 and 4 satisfying all conditions above, they contain letters "a", "c"
and "c". We may form a palindrome "cac".

上一篇:codeforces 570 D. Tree Requests (dfs)


下一篇:Oracle PIVOT 行转列方法