luogu题解 P3950部落冲突--树链剖分

题目链接

https://www.luogu.org/problemnew/show/P3950

分析

大佬都用LCT，我太弱只会树链剖分

一个很裸的维护边权树链剖分题.按照套路,对于一条边\(<u,v>(dep(u)<dep(v))\),让它边权加1就在\(v\)点处+1，将边的问题转化为点的问题

然后对于C，U操作，线段树单点修改，Q操作区间查询

注意

• 询问\(u,v(dep(u)>dep(v))\)点之间是否联通区间查询时注意是查询\([u,son[v]]\)的和,忽然发现NOI赛场上Day2用树链剖分写得暴力为什么错了。。。

• 单点修改注意是修改\(dfn[x]\)那个点,查了好久的错

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <iostream>
#include <vector>
#include <cmath>
#define ll long long 
#define ri register int
using namespace std;
template <class T>inline void read(T &x){
  x=0;int ne=0;char c;
  while(!isdigit(c=getchar()))ne=c==‘-‘;
  x=c-48;
  while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
  x=ne?-x:x;return;
}  
const int maxn=300005;
const int inf=0x7fffffff;
struct Edge{
  int ne,to;
}edge[maxn<<1];
int h[maxn],num_edge=1;
inline void add_edge(int f,int to){
  edge[++num_edge].ne=h[f];
  edge[num_edge].to=to;
  h[f]=num_edge;
}
int dfn[maxn],tot=0,top[maxn],dep[maxn],fa[maxn],son[maxn],size[maxn];
void dfs_1(int now){
 int v;size[now]=1;
 for(ri i=h[now];i;i=edge[i].ne){
      v=edge[i].to;
      if(v==fa[now])continue;
      fa[v]=now,dep[v]=dep[now]+1;
      dfs_1(v);
      size[now]+=size[v];
      if(!son[now]||size[son[now]]<size[v])son[now]=v;
  }
  return ;
}
void dfs_2(int now,int t){
  int v;dfn[now]=++tot,top[now]=t;
  if(!son[now])return ;
  dfs_2(son[now],t);
  for(ri i=h[now];i;i=edge[i].ne){
      v=edge[i].to;
      if(v==fa[now]||v==son[now])continue;
      dfs_2(v,v);
  }
  return ;
}
int sum[maxn<<2],L,R,dta,t;
void update(int now,int l,int r){
  if(l==r){
      sum[now]+=dta;
      return ;
  }
  int mid=(l+r)>>1;
  if(t<=mid)update(now<<1,l,mid);
  else update(now<<1|1,mid+1,r);
  sum[now]=sum[now<<1]+sum[now<<1|1];
  return ;
}
int query(int now,int l,int r){
  if(L<=l&&r<=R){
      return sum[now];
  }
  int mid=(l+r)>>1,ans=0;
  if(L<=mid)ans+=query(now<<1,l,mid);
  if(mid<R)ans+=query(now<<1|1,mid+1,r);
  //cout<<l<<‘ ‘<<r<<‘ ‘<<ans<<endl;
  return ans;
}
int n,m;
struct War{
  int x,y;
}war[maxn];
int query_path(int x,int y){
  int tmp=0;
  while(top[x]!=top[y]){
      if(dep[top[x]]<dep[top[y]])swap(x,y);
      L=dfn[top[x]],R=dfn[x];
      tmp=query(1,1,n);
      //cout<<tmp<<endl;
      if(tmp!=0)return 0;
      x=fa[top[x]];
  }
  if(dep[x]>dep[y])swap(x,y);
  L=dfn[x]+1,R=dfn[y];
  if(L>R)return 1;
  tmp=query(1,1,n);//puts("f***");
  //cout<<tmp<<endl;
  if(tmp!=0)return 0;
  return 1;
}
inline void update_path(int x,int y,int z){
  dta=z;
  if(dep[x]<dep[y])swap(x,y);
  t=dfn[x];
  update(1,1,n);
  //L=1,R=n;
  //printf("%d\n",query(1,1,n));
  return ;
}
int main(){
  char opt[5];
  int x,y,z,cnt=0;
  read(n),read(m);
  for(ri i=1;i<n;i++){
      read(x),read(y);
      add_edge(x,y);
      add_edge(y,x);
  }
  dep[1]=1,fa[1]=0;
  dfs_1(1);
  dfs_2(1,1);
  memset(sum,0,sizeof(sum));
  for(ri i=1;i<=m;i++){
      scanf("%s",opt);
      //cout<<opt<<endl;
      if(opt[0]==‘Q‘){
          //puts("wtf");
          read(x),read(y);
          //L=1,R=n;
          //printf("%d\n",query(1,1,n));
          if(query_path(x,y))puts("Yes");
          else puts("No");
      }
      else if(opt[0]==‘C‘){
          read(x),read(y);
          war[++cnt].x=x;
          war[cnt].y=y;
          update_path(x,y,1);
      }
      else{
          read(z);
          x=war[z].x,y=war[z].y;
          update_path(x,y,-1);
      }
  }
  return 0;
}

luogu题解 P3950部落冲突--树链剖分

原文：https://www.cnblogs.com/Rye-Catcher/p/9351619.html