[LuoguP3950] 部落冲突
emmmm虽然上次被线段树合并给恶心了qwq但是还是不能放弃数据结构呀。于是记录一下树链剖分吧哈哈哈哈,比较好想的一道模板题目,被输入卡了很多TOO SHORT ON LINE 1emmmm最后把scanf(“%c%c%d”,&tmp,&c,&x);改成了scanf(“%c”,s,&x);就可以了,看来是windows编程环境与linux评测环境的问题emmm
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define mid ((l+r)>>1)
#define maxn 300005
using namespace std;
struct node{
int to;
node*next;
}*con[maxn];
void addedge(int x,int y){
node*p=new node;
p->to=y;
p->next=con[x];
con[x]=p;
}
int n,m,x,y,tim,zz;
bool vis[maxn];
int sz[maxn],hs[maxn],hd[maxn],fa[maxn],de[maxn],dfn[maxn];
struct segtree;
segtree *Nul;
struct segtree{
int sum,lazy;
segtree*so[2];
segtree(){
so[0]=so[1]=Nul;
sum=0;
}
void update() {sum=so[0]->sum+so[1]->sum;}
void build(int l,int r){
if(l==r) return;
(so[0]=new segtree)->build(l,mid);
(so[1]=new segtree)->build(mid+1,r);
update();
}
void calc(int l,int r,int tag){
lazy+=tag;
sum+=(r-l+1)*tag;
}
void pushdown(int l,int r){
if(so[0]!=Nul) so[0]->calc(l,r,lazy);
if(so[1]!=Nul) so[1]->calc(l,r,lazy);
lazy=0;
}
void modify(int l,int r,int lx,int rx,int num){
// cout<<l<<" "<<r<<" "<<lx<<" "<<rx<<endl;
if(l==lx&&r==rx){
calc(l,r,num);
return;
}
pushdown(l,r);
if(lx>mid) so[1]->modify(mid+1, r, lx, rx, num);
else if(rx<=mid) so[0]->modify(l, mid, lx, rx, num);
else {so[0]->modify(l, mid, lx, mid, num);so[1]->modify(mid+1, r, mid+1, rx, num);}
update();
}
int query(int l,int r,int lx,int rx){
if(l==lx&&r==rx)
return sum;
pushdown(l,r);
if(lx>mid) return so[1]->query(mid+1,r,lx,rx);
else if(rx<=mid) return so[0]->query(l,mid,lx,rx);
else return so[0]->query(l,mid,lx,mid)+so[1]->query(mid+1,r,mid+1,rx);
}
}*xtr;
void dfs1(int v){
vis[v]=true;
int mxsz=0;
sz[v]=1;
for(node*p=con[v];p;p=p->next)
if(!vis[p->to]) {
fa[p->to]=v;
de[p->to]=de[v]+1;
dfs1(p->to);
sz[v]+=sz[p->to];
if(sz[p->to]>mxsz) {hs[v]=p->to;mxsz=sz[p->to];}
}
return;
}
void dfs2(int v){
vis[v]=true;
dfn[v]=++tim;
for(node*p=con[v];p;p=p->next)
if(hs[v]==p->to) {
hd[p->to]=hd[v];
dfs2(p->to);
}
for(node*p=con[v];p;p=p->next)
if(!vis[p->to]&&hs[v]!=p->to)
dfs2(p->to);
}
bool qry(int x,int y){
while(hd[x]!=hd[y]){
if(de[hd[x]]<de[hd[y]]) swap(x,y);
if(xtr->query(1,n,dfn[hd[x]],dfn[x])) return false;
x=fa[hd[x]];
}
if(x==y){
return true;
}
if(de[x]<de[y]) swap(x,y);
if(xtr->query(1,n,dfn[y]+1,dfn[x])) return false;
return true;
}
void war(int x,int y,int tmp){
while(hd[x]!=hd[y]){
if(de[hd[x]]<de[hd[y]]) swap(x,y);
xtr->modify(1, n, dfn[hd[x]], dfn[x], tmp);
x=fa[hd[x]];
}
if(x==y) return;
if(de[x]<de[y]) swap(x,y);
xtr->modify(1, n, dfn[y]+1, dfn[x], tmp);
}
struct suibian{
int x,y;
}wrs[maxn];
int main(){
scanf("%d%d",&n,&m);
Nul=new segtree;
Nul->so[0]=Nul;Nul->so[1]=Nul;Nul->lazy=Nul->sum=0;
(xtr=new segtree)->build(1,n);
for(int i=1;i<=n;++i) hd[i]=i;
for(int i=1;i<n;++i){
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
de[1]=1;
dfs1(1);
memset(vis,0,sizeof(vis));
dfs2(1);
char s[5],c;
while(m--){
scanf("%s%d",s,&x);
if(s[0]=='Q'){
scanf("%d",&y);
if(qry(x,y)) printf("Yes\n");
else printf("No\n");
}
if(s[0]=='C'){
scanf("%d",&y);
wrs[++zz].x=x;wrs[zz].y=y;
war(x,y,1);
}
if(s[0]=='U')
war(wrs[x].x,wrs[x].y,-1);
}
return 0;
}