CF 570D. Tree Requests [dsu on tree]

时间:2022-08-30 16:01:42

[传送门](http://codeforces.com/contest/570/problem/D)
题意:
一棵树,询问某棵子树指定深度的点能否构成回文


当然不用dsu on tree也可以做

dsu on tree的话,维护当前每一个深度每种字母出现次数和字母数,我直接用了二进制....

一开始dfs没有判断重儿子T了一次

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
#define pii pair<int, ll>
#define MP make_pair
#define fir first
#define sec second
const int N=5e5+5;
int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
return x*f;
} int n, a[N], Q, x;
char s[N];
vector<pii> q[N];
int ans[N];
struct edge{int v, ne;}e[N<<1];
int cnt, h[N];
inline void ins(int u, int v) {
e[++cnt]=(edge){v, h[u]}; h[u]=cnt;
}
int size[N], mx[N], deep[N], big[N];
void dfs(int u) {
size[u]=1;
for(int i=h[u];i;i=e[i].ne) {
deep[e[i].v] = deep[u]+1;
dfs(e[i].v);
size[u] += size[e[i].v];
if(size[e[i].v] > size[mx[u]]) mx[u] = e[i].v;
}
} pii f[N];
void update(int u, int val) {
f[ deep[u] ].fir += val;
f[ deep[u] ].sec ^= (1<<(a[u]));
for(int i=h[u];i;i=e[i].ne) if(!big[e[i].v]) update(e[i].v, val);
}
inline int one(int n) {
int ans=0;
while(n) n&=(n-1), ans++;
return ans;
}
inline int cal(int d) {return f[d].sec == 0 || (one(f[d].sec) == 1 && (f[d].fir & 1) );}
void dfs(int u, int keep) {
for(int i=h[u];i;i=e[i].ne)
if(e[i].v != mx[u]) dfs(e[i].v, 0);
if(mx[u]) dfs(mx[u], 1), big[mx[u]]=1;
update(u, 1);
for(int i=0; i<(int)q[u].size(); i++) ans[q[u][i].sec] = cal(q[u][i].fir);
big[mx[u]]=0;
if(!keep) update(u, -1);
} int main() {
//freopen("in","r",stdin);
n=read(); Q=read();
for(int i=2; i<=n; i++) ins(read(), i);
scanf("%s",s+1);
for(int i=1; i<=n; i++) a[i] = s[i]-'a';
for(int i=1; i<=Q; i++) x=read(), q[x].push_back(MP(read(), i));
deep[1] = 1; dfs(1);
dfs(1, 1);
for(int i=1; i<=Q; i++) puts(ans[i] ? "Yes" : "No");
}

CF 570D. Tree Requests [dsu on tree]的更多相关文章

  1. CF 600E&period; Lomsat gelral&lpar;dsu on tree&rpar;

    解题思路 \(dsu\) \(on\) \(tree\)的模板题.暴力而优雅的算法,轻儿子的信息暴力清空,重儿子的信息保留,时间复杂度\(O(nlogn)\) 代码 #include<iostr ...

  2. Codeforces Round &num;316 &lpar;Div&period; 2&rpar; D&period; Tree Requests&lpar;dsu&rpar;

    题目链接 题意:对于m次询问 求解以vi为根节点 深度为hi的的字母能不能组合成回文串. 思路:暴力dsu找一边 简直就是神技! #include<bits/stdc++.h> #defi ...

  3. CF 208E&period; Blood Cousins &lbrack;dsu on tree 倍增&rsqb;

    题意:给出一个森林,求和一个点有相同k级祖先的点有多少 倍增求父亲然后和上题一样还不用哈希了... #include <iostream> #include <cstdio> ...

  4. HDU6504 Problem E&period; Split The Tree【dsu on tree】

    Problem E. Split The Tree Problem Description You are given a tree with n vertices, numbered from 1 ...

  5. 初涉DSU on tree

    早先以为莫队是个顶有用的东西,不过好像树上莫队(不带修)被dsu碾压? dsu one tree起源 dsu on tree是有人在cf上blog上首发的一种基于轻重链剖分的算法,然后好像由因为这个人 ...

  6. dsu on tree入门

    先瞎扯几句 说起来我跟这个算法好像还有很深的渊源呢qwq.当时在学业水平考试的考场上,题目都做完了不会做,于是开始xjb出题.突然我想到这么一个题 看起来好像很可做的样子,然而直到考试完我都只想出来一 ...

  7. CF 570 D&period; Tree Requests

    D. Tree Requests http://codeforces.com/problemset/problem/570/D 题意: 一个以1为根的树,每个点上有一个字母(a-z),每次询问一个子树 ...

  8. Codeforces 570D - Tree Requests(树上启发式合并)

    570D - Tree Requests 题意 给出一棵树,每个节点上有字母,查询 u k,问以 u 为根节点的子树下,深度为 k 的所有子节点上的字母经过任意排列是否能构成回文串. 分析 一个数组 ...

  9. CF 741D&period; Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths &lbrack;dsu on tree 类似点分治&rsqb;

    D. Arpa's letter-marked tree and Mehrdad's Dokhtar-kosh paths CF741D 题意: 一棵有根树,边上有字母a~v,求每个子树中最长的边,满 ...

随机推荐

  1. 当web&period;config文件放置在共享目录下(UNC),启动IIS会提示有错误信息500&period;19,伴随有错误代码0x80070003和错误代码0x80070005的解决办法

    最近遇到一个很有意思的使用环境,操作人员将所有的网站应用内容投放到共享存储里面,并且使用微软的SMB协议将其以CIFS的方式共享出来,使用Windows Server 2008 R2的IIS将其连接起 ...

  2. Soket编程

    基本概念 lIP地址 每台联网的电脑都有一个唯一的IP地址. 长度32位,分为四段,每段8位,用十进制数字表示,每段范围 0 ~ 255 特殊IP:127.0.0.1 用户本地网卡测试 版本:V4(3 ...

  3. JMeter学习(二十五)HTTP属性管理器HTTP Cookie Manager、HTTP Request Defaults

    Test Plan的配置元件中有一些和HTTP属性相关的元件:HTTP Cache Manager.HTTP Authorization Manager.HTTP Cookie Manager.HTT ...

  4. Design Patterns

    经典的<设计模式>一书归纳出23种设计模式,本文按<易学设计模式>一书归纳分类如下:1.创建型模式 前面讲过,社会化的分工越来越细,自然在软件设计方面也是如此,因此对象的创建和 ...

  5. IntelliJ IDEA 13怎么创建JAVA SE项目

    如下图,直接下一步,如果需要的话可以选择建立Main函数:

  6. Nagios监控memcached

    下载地址: http://search.cpan.org/CPAN/authors/id/Z/ZI/ZIGOROU/Nagios-Plugins-Memcached-0.02.tar.gz http: ...

  7. css超简单实现div页面居中【适合做弹出框】

    1.前言 现在项目中用到弹出框的话大部分都是直接用控件的.不过有控件虽方便,但有时候会有冲突的地方.我上次用layui的弹出框控件,然后也用到了百度的编辑器uEditor,然后一切都好好的,结果编辑赋 ...

  8. bootstrap-3-验证表单

    js: $('#nqs-add-userxinxi-form').bootstrapValidator({ message: 'This value is not valid', excluded : ...

  9. 转 c&num;中stringbuilder的使用

    String   对象是不可改变的.每次使用   System.String   类中的方法之一时,都要在内存中创建一个新的字符串对象,这就需要为该新对象分配新的空间.在需要对字符串执行重复修改的情况 ...

  10. MongoDB常用方法

    一.查询 find方法 db.collection_name.find(); 查询所有的结果: select * from users; db.users.find(); 指定返回那些列(键): se ...