CF 570 D. Tree Requests
2024-09-04 16:32:55
D. Tree Requests
http://codeforces.com/problemset/problem/570/D
题意:
一个以1为根的树,每个点上有一个字母(a-z),每次询问一个子树内深度为h的点是否可以构成回文串。(深度是到1的深度,没有也算,空回文串)
分析:
dsu on tree。询问子树信息。
判断是否构成回文:出现奇数次的字符小于等于1个。
代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define pa pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ; int head[N], nxt[N], to[N], En;
int fa[N], siz[N], son[N], deth[N], ans[N], cnt[N][], ch[N];
char s[N];
vector< pa > q[N]; void add_edge(int u,int v) {
++En; to[En] = v; nxt[En] = head[u]; head[u] = En;
} void dfs(int u,int fa) {
siz[u] = ;
deth[u] = deth[fa] + ;
for (int i=head[u]; i; i=nxt[i]) {
int v = to[i];
dfs(v, u);
siz[u] += siz[v];
if (!son[u] || siz[son[u]] < siz[v]) son[u] = v;
}
} void add(int u) {
cnt[deth[u]][ch[u]] ++;
}
void Calc(int u) {
add(u);
for (int i=head[u]; i; i=nxt[i]) Calc(to[i]);
}
void Clear(int u) {
cnt[deth[u]][ch[u]] --;
for (int i=head[u]; i; i=nxt[i]) Clear(to[i]);
} void solve(int u,bool c) {
for (int i=head[u]; i; i=nxt[i])
if (to[i] != son[u]) solve(to[i], );
if (son[u]) solve(son[u], ); for (int i=head[u]; i; i=nxt[i])
if (to[i] != son[u]) Calc(to[i]);
add(u); for (int i=,sz=q[u].size(); i<sz; ++i) {
int flag = , id = q[u][i].second, h = q[u][i].first;
for (int j=; j<; ++j) if (cnt[h][j] & ) flag ++;
ans[id] = (flag <= );
} if (!c) Clear(u);
} int main() {
int n = read(), Q = read();
for (int i=; i<=n; ++i) {
int u = read();
add_edge(u, i);
}
scanf("%s",s + );
for (int i=; i<=n; ++i) ch[i] = s[i] - 'a';
for (int i=; i<=Q; ++i) {
int v = read(), h = read();
q[v].push_back(mp(h, i));
}
dfs(, );
solve(, );
for (int i=; i<=Q; ++i) puts(ans[i] ? "Yes" : "No");
return ;
}
最新文章
- 数据存储之CoreData
- sql查询最大的见多了,查询第二的呢???
- LINUX下NFS系统的安装配置
- Python调用微博API
- Office 365开发概述及生态环境介绍(一)
- 4.在浏览器中解析XML
- java面向对象--抽象类和接口
- ios开发 oc 的类方法与对象方法
- 微信小程序开发过程中一些经验总结
- QQ信鸽推送
- JVM-垃圾收集的过程
- Ionic1开发环境配置ji
- RxJava(11-线程调度Scheduler)
- Hadoop记录- zookeeper 监控指标
- nfs+keepalived高可用
- Jquery 组 checkbox双向控制与tr变色
- js中call、apply和bind的区别
- windows 运行hadoop的WordCount报nativeio.NativeIO$Windows.createDirectoryWithMode0(Ljava/lang/String;I)
- L与_T
- Python核心编程 | 装饰器