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