题面

DSU on tree确实很厉害,然后这变成了一道裸题(逃

还是稍微说一下流程吧,虽然我那个模板汇总里写过

DSU on tree可以以$O(n\log n)$的复杂度解决树上子树统计问题,它这样工作:

前置工作:对树进行轻重链剖分

1.递归求解所有的轻儿子,在回溯时消去影响

2.递归进入重儿子,在回溯时不消去影响

3.暴力统计子树信息

4.回答询问并回溯

根据轻重链剖分的性质,复杂度$O(n\log n)$

 #include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
vector<pair<int,int> > qry[N];
int siz[N],dep[N],imp[N],sta[N],vis[N],outp[N];
int p[N],noww[*N],goal[*N];
int n,m,t1,t2,rd,cnt;
char str[N];
void Link(int f,int t)
{
noww[++cnt]=p[f];
goal[cnt]=t,p[f]=cnt;
noww[++cnt]=p[t];
goal[cnt]=f,p[t]=cnt;
}
int Bitcount(int s)
{
int ret=;
while(s)
ret++,s-=s&-s;
return ret;
}
void DFS(int nde,int fth,int dth)
{
int tmp=;
siz[nde]=,dep[nde]=dth;
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=fth)
{
DFS(goal[i],nde,dth+);
siz[nde]+=siz[goal[i]];
if(siz[goal[i]]>tmp)
tmp=siz[goal[i]],imp[nde]=goal[i];
}
}
void Count(int nde,int fth)
{
sta[dep[nde]]^=<<(str[nde]-'a');
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=fth&&!vis[goal[i]])
Count(goal[i],nde);
}
void Getans(int nde,int fth,int hvy)
{
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=fth&&goal[i]!=imp[nde])
Getans(goal[i],nde,);
if(imp[nde])
Getans(imp[nde],nde,),vis[imp[nde]]=true;
Count(nde,fth);
vector<pair<int,int> >::iterator it;
for(it=qry[nde].begin();it!=qry[nde].end();it++)
{
int dth=it->second;
outp[it->first]=(Bitcount(sta[dth])<=);
}
if(imp[nde]) vis[imp[nde]]=false;
if(!hvy) Count(nde,fth);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
scanf("%d",&t1),Link(t1,i+);
scanf("%s",str+);
for(int i=;i<=m;i++)
{
scanf("%d%d",&t1,&t2);
qry[t1].push_back(make_pair(i,t2));
}
DFS(,,),Getans(,,);
for(int i=;i<=m;i++)
outp[i]?puts("Yes"):puts("No");
return ;
}

最新文章

  1. 集成 Kendo UI for Angular 2 控件
  2. 将AJAX返回值纵向排序赋值给Table标签
  3. 查询sqlserver 正在执行的sql语句的详细信息
  4. linux poll 学习
  5. springmvc的系统学习之配置方式
  6. Python工程文件中的名词解释---Module与Package的区别
  7. java this 隐式参数
  8. WebApi 自定义过滤器实现支持AJAX跨域的请求
  9. Elasticlunr.js 简单介绍
  10. Json多层对象访问
  11. debug_backtrace
  12. JDBC+Servlet+JSP的学生案例增删改查
  13. 关于 ajax
  14. Typescript学习笔记(一)基础类型
  15. Hadoop---集群的时间同步
  16. memcached 一致性hash原理
  17. 《Go语言实战》Go 类型:基本类型、引用类型、结构类型、自定义类型
  18. Hbase 学习(四) hbase客户端设置缓存优化查询
  19. Ubuntu 14.04 安装adobe flash player
  20. springmvc自己定义拦截器

热门文章

  1. Netty源码分析第3章(客户端接入流程)----&gt;第2节: 处理接入事件之handle的创建
  2. Metasploit拿Shell
  3. 点斜杠 &amp; 如何查看linux程序安装位置 dpkg -L yyy
  4. PSP总结
  5. Windows下Visual Studio2017之AI环境搭建
  6. fullPage全屏高度自适应
  7. “Gogoing”改进方案
  8. Java导出引用jar包的文件
  9. mysql密码忘记解决方案
  10. 【贪心算法】POJ-2393 简单贪心水题