WISCO信息组NOIP模拟赛-部落冲突
2024-09-10 01:41:37
传送门
首先肯定考虑树剖，这里没有要求区间加，所以可以用树状数组维护，不会卡常的
这里是边权，可以转化为点权：让每条边连接的较深的节点的点权等于边权即可，然后计算的时候减去lca
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define MAXN 300005
#define LOG 20
using namespace std;
int read(){
int x=;char ch=getchar();
while(ch<''||ch>''){ch=getchar();}
while(ch>=''&&ch<=''){x=x*+(ch^);ch=getchar();}
return x;
}
int n,T;
int a[MAXN],dat[MAXN];
int dep[MAXN],size[MAXN],gs[MAXN],fa[][MAXN];
int top[MAXN],tree[MAXN],pre[MAXN],tot;
int first[MAXN],nxt[MAXN<<],to[MAXN<<],cnt;
int id[MAXN],tmp; void add(int x,int y){
nxt[++cnt]=first[x];first[x]=cnt;to[cnt]=y;
nxt[++cnt]=first[y];first[y]=cnt;to[cnt]=x;
}
int lca(int x,int y){
if(dep[x]<dep[y]){
swap(x,y);
}
for(int k=dep[x]-dep[y],p=;k;k>>=,p++){
if(k&){
x=fa[p][x];
}
}
if(x==y){
return x;
}
for(int k=LOG-;k>=;k--){
if(fa[k][x]!=fa[k][y]){
x=fa[k][x],y=fa[k][y];
}
}
return fa[][x];
}
void change(int k,int x){
while(k<=n){
dat[k]+=x;
k+=(k&-k);
}
}
int query(int k){
int ret=;
while(k>=){
ret+=dat[k];
k-=(k&-k);
}
return ret;
}
void dfs1(int x){
size[x]=;
for(int e=first[x];e;e=nxt[e]){
int y=to[e];
if(y==fa[][x]){
continue;
}
fa[][y]=x;
dep[y]=dep[x]+;
dfs1(y);
size[x]+=size[y];
if(size[y]>size[gs[x]]){
gs[x]=y;
}
}
}
void dfs2(int x,int t){
top[x]=t;
tree[x]=(++tot);
pre[tot]=x;
if(!gs[x]){
return;
}
dfs2(gs[x],t);
for(int e=first[x];e;e=nxt[e]){
int y=to[e];
if(y==fa[][x]||y==gs[x]){
continue;
}
dfs2(y,y);
}
}
int ask(int x,int y){
int f1=top[x],f2=top[y];
if(dep[f1]<dep[f2]){
swap(x,y),swap(f1,f2);
}
int ret=-a[lca(x,y)];
while(f1!=f2){
ret+=query(tree[x])-query(tree[f1]-);
x=fa[][f1]; f1=top[x];
if(dep[f1]<dep[f2]){
swap(x,y),swap(f1,f2);
}
}
if(dep[x]<dep[y]){
swap(x,y);
}
ret+=query(tree[x])-query(tree[y]-);
return (ret<=);
}
void init(){
n=read();T=read();
for(int i=;i<n;i++){
int x=read(),y=read();
add(x,y);
}
dfs1();
dfs2(,);
for(int k=;k<LOG;k++){
for(int i=;i<=n;i++){
fa[k][i]=fa[k-][fa[k-][i]];
}
}
}
void solve(){
char ch[];
while(T--){
scanf("%s",ch);
int x=read();
if('Q'==ch[]){
int y=read();
if(ask(x,y)){
printf("Yes\n");
}
else{
printf("No\n");
}
}
else if('C'==ch[]){
int y=read();
if(dep[x]<dep[y]){
swap(x,y);
}
change(tree[x],);
a[x]++;
id[++tmp]=x;
}
else{
x=id[x];
change(tree[x],-);
a[x]--;
}
}
}
int main()
{
init();
solve();
return ;
}
树剖AC
也可以是树上差分，用树状数组+dfs序，本质上是差不多的
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define MAXN 300005
#define LOG 20
using namespace std;
int read(){
int x=;char ch=getchar();
while(ch<''||ch>''){ch=getchar();}
while(ch>=''&&ch<=''){x=x*+(ch^);ch=getchar();}
return x;
}
int n,T;
int first[MAXN],nxt[MAXN<<],to[MAXN<<],cnt;
int pin[MAXN],pout[MAXN],tot;
int dat[MAXN<<];
int fa[LOG][MAXN],dep[MAXN];
int id[MAXN],tmp;
void change(int k,int x){
while(k<=(n<<)){
dat[k]+=x;
k+=(k&-k);
}
}
int query(int k){
int ret=;
while(k>=){
ret+=dat[k];
k-=(k&-k);
}
return ret;
}
void add(int x,int y){
nxt[++cnt]=first[x];first[x]=cnt;to[cnt]=y;
nxt[++cnt]=first[y];first[y]=cnt;to[cnt]=x;
}
int lca(int x,int y){
if(dep[x]<dep[y]){
swap(x,y);
}
for(int k=dep[x]-dep[y],p=;k;k>>=,p++){
if(k&){
x=fa[p][x];
}
}
if(x==y){
return x;
}
for(int k=LOG-;k>=;k--){
if(fa[k][x]!=fa[k][y]){
x=fa[k][x],y=fa[k][y];
}
}
return fa[][x];
}
void dfs(int x){
pin[x]=(++tot);
for(int e=first[x];e;e=nxt[e]){
int y=to[e];
if(y==fa[][x]){
continue;
}
dep[y]=dep[x]+;
fa[][y]=x;
dfs(y);
}
pout[x]=(++tot);
}
int ask(int x,int y){
int t=query(pin[x])+query(pin[y])-*query(pin[lca(x,y)]);
return (t<=);
}
void init(){
n=read(); T=read();
for(int i=;i<n;i++){
int x=read(),y=read();
add(x,y);
}
dfs();
for(int k=;k<LOG;k++){
for(int i=;i<=n;i++){
fa[k][i]=fa[k-][fa[k-][i]];
}
}
}
void solve(){
char ch[]={};
while(T--){
scanf("%s",ch);
int x=read();
if('Q'==ch[]){
int y=read();
if(ask(x,y)){
printf("Yes\n");
}
else{
printf("No\n");
}
}
else if('C'==ch[]){
int y=read();
if(dep[x]<dep[y]){
swap(x,y);
}
change(pin[x],);
change(pout[x]+,-);
id[++tmp]=x;
}
else{
x=id[x];
change(pin[x],-);
change(pout[x]+,);
}
}
}
int main()
{
// freopen("data.in","r",stdin);
init();
solve();
return ;
}
树上差分AC
最新文章
- linux磁盘空间查询
- 获取shell脚本自身所在目录的Shell脚本分享
- 数据库服务器的安装 (MySQL Server 5.7) :
- knockoutjs关键点
- innerHTML在IE中报错
- POJ 3233 Matrix Power Series(矩阵高速功率+二分法)
- 在windos 环境下安装
- CSS学习（一）---使用CSS的四种方式
- 三层架构和MVC一样吗？（区别）
- Taro 代码及功能，需要注意的地方
- 官网下载的Struts 2解压后缺少xwork-core.jar文件
- 怎么才能使服务器Nginx（或者Apache）支持字体文件
- [codeup] 1128 出租车费
- 范数 L1 L2
- Redis Cluster笔记
- E题:Water Problem(快速幂模板)
- Redis_NoSql分布式数据库CAP原理
- const 与过载
- BZOJ2005:[NOI2010]能量采集(莫比乌斯反演,欧拉函数)
- CSS权威指南(第3版)