P4334

标签：return int Trees st dep Lca P4334

先建出原图的广义圆方树，设 \(C(A, B)\) 为\(A,B\) 所在点双的方点。

本文中的路径均指在广义圆方树的简单路径。

容易发现操作 2 的本质是询问 \(C\) 是否在 \(A\) 至 \(B\) 的路径上。

对于操作 1 ，我们发现若删去连接 \(G_1\) 和 \(G_2\) 之间的道路后 \(A\) 和 \(B\) 不连通当且仅当连接 \(G_1\) 和 \(G_2\) 之间的道路是割边（\(C(G_1, G_2)\) 的度数为 \(2\)）且 \(C(G_1, G_2)\) 在\(A\) 至 \(B\) 的路径上。

我们可以用 LCA 进行判定，时间复杂度 \(O((n+q)\log n)\)，瓶颈在于求 LCA。

#include <bits/stdc++.h>
using namespace std;
struct Edge{int nt, to;};
const int N=1e6+11;
struct Tree{
  int cnt, h[N]; Edge e[N<<1];
  int dep[N], st[N][19], du[N];
  void link(int u, int v){
    // printf("Node %d -> %d\n", u, v);
    du[u]++;
    e[++cnt]={h[u], v}, h[u]=cnt;
    e[++cnt]={h[v], u}, h[v]=cnt;
  }
  void dfs(int u, int Fa){
    dep[u]=dep[Fa]+1, st[u][0]=Fa;
    for(int i=1; i<19; i++)
      st[u][i]=st[st[u][i-1]][i-1];
    for(int i=h[u], v; i; i=e[i].nt){
      if((v=e[i].to)==Fa)continue;
      dfs(v, u);
    }
  }
  int Lca(int x, int y){
    if(dep[x]<dep[y])swap(x, y);
    for(int i=18; i>=0; i--)
      if(dep[st[x][i]]>=dep[y])x=st[x][i];
    if(x==y)return x;
    for(int i=18; i>=0; i--)
      if(st[x][i]!=st[y][i])
        x=st[x][i], y=st[y][i];
    return st[x][0];
  }
  bool check(int x, int y){
    int l=Lca(x, y);
    return l==x||l==y;
  }
  bool solve2(int A, int B, int C){
    int LCA=Lca(A, B);
    if(Lca(LCA, C)!=LCA)return 0;
    if(Lca(A, C)==C||Lca(B, C)==C)return 1;
    return 0;
  }
  bool solve1(int A, int B, int P, int Q){
    if(dep[Q]==dep[P])return 1; // 方点只会连接 P, Q 两个点，深度一定不同。
    if(dep[Q]<dep[P])swap(Q, P);
    int Mid=st[Q][0];
    if(du[Mid]!=2)return 1;
    return !solve2(A, B, Mid);
  }
}Trees;
struct Graph{
  int cnt, h[N], Node; Edge e[N<<1];
  void link(int u, int v){
    e[++cnt]={h[u], v}, h[u]=cnt;
    e[++cnt]={h[v], u}, h[v]=cnt;
  }
  int dfn[N], low[N], dfnt, Stack[N], Top;
  void Tarjan(int u){
    dfn[u]=low[u]=++dfnt, Stack[++Top]=u;
    for(int i=h[u]; i; i=e[i].nt){
      int v=e[i].to;
      if(!dfn[v]){
        Tarjan(v);
        low[u]=min(low[u], low[v]);
        if(low[v]>=dfn[u]){
          Node++; Trees.link(Node, u);
          for(int x=0; x!=v; Top--)
            x=Stack[Top], Trees.link(Node, x);
        }
      }
      else
        low[u]=min(low[u], dfn[v]);
    }
  }
  void Solve(int tt){Node=tt, Tarjan(1), Top=0;}
}Graphs;
int n, m, q;
int main(){
  cin>>n>>m;
  for(int i=1, x, y; i<=m; i++)
    cin>>x>>y, Graphs.link(x, y);
  Graphs.Solve(n);
  Trees.dfs(1, 0);
  cin>>q;
  while(q--){
    int op;
    cin>>op;
    if(op==1){
      int a, b, p, q;
      cin>>a>>b>>p>>q;
      puts(Trees.solve1(a, b, p, q)?"yes":"no");
    }
    else{
      int a, b, c;
      cin>>a>>b>>c;
      puts(!Trees.solve2(a, b, c)?"yes":"no");
    }
  }
  return 0;
}

标签：return,int,Trees,st,dep,Lca,P4334
From： https://www.cnblogs.com/dadidididi/p/17365918.html