1-C23【模板】虚树

#include<bits/stdc++.h>//scy代码20250214
using namespace std;
const int N=1e5+10;
vector<int>G[N],G2[N];//G2为虚树
int n,k,q,a[N],ans;
int tsp,dfn[N],dep[N],D,st[N][20],sta[N],top;
void dfs(int x, int xfa) 
{
    dfn[x]=++tsp;
    dep[x]=dep[xfa]+1;
    st[x][0]=xfa;for(int i=1; i<=D; i++)st[x][i]=st[st[x][i-1]][i-1];
    for(int y:G[x])if(y!=xfa)dfs(y,x);
}
int LCA(int x, int y) 
{
    if(dep[x]<dep[y])swap(x, y);
    for(int i=D;i>=0;i--)if(dep[st[x][i]]>=dep[y])x=st[x][i];
    if(x==y) return y;
    for(int i=D;i>=0;i--)if(st[x][i]!=st[y][i])x=st[x][i], y=st[y][i];
    return st[x][0];
}
bool cmp(int x,int y) {return dfn[x]<dfn[y];}
 
void build()//建虚树 
{
    sort(a+1,a+k+1,cmp); //按dfs序排序
    sta[top=1]=1;if(a[1]!=1) sta[++top]=a[1]; //根节点入栈
    for(int i=2;i<=k;i++)//枚举查询点 
    { 
        int lca=LCA(sta[top],a[i]);
        while(top>1 && !(dep[sta[top-1]] < dep[lca]) )G2[sta[top-1]].push_back(sta[top]), top--;
        if(lca!=sta[top])G2[lca].push_back(sta[top]), top--,sta[++top]=lca;
        sta[++top]=a[i];
    }
    for(int i=1;i<top;++i) G2[sta[i]].push_back(sta[i+1]);//对最后一条链连边
}
bool mk[N];
int DP(int x)//树形DP 
{
    int res=0,cnt=0;
    for(int y:G2[x])
    {
        res+=DP(y);
        cnt+=mk[y];
    }
    G2[x].clear();
    return (mk[x]) ? res+cnt : (mk[x]=(cnt==1),res+(cnt>=2));
    //如果x是查询点，则孩子节点有多少个查询点就需要断多少次（删除x和 为查询点的孩子之间 未出现在虚树中的点）
    //如果x不是查询点，则分情况：1、只有一个孩子是查询点，那么不需要断，但x“升级”为查询点；2、>=2个孩子节点为查询点，那么就删除x
}
int main() 
{
    scanf("%d",&n);
    for(int i=1,x,y; i<n; i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);G[y].push_back(x);
    }
    dep[0]=0;D=log2(n);dfs(1,0);
    scanf("%d",&q);while(q--)
    {
        scanf("%d",&k);
        memset(mk,0,sizeof(mk));
        for(int i=1;i<=k;i++)scanf("%d",&a[i]),mk[a[i]]=1;
        bool flag=0; for(int i=1;i<=k;i++)if(mk[ st[a[i]][0] ]==1){flag=1;break;} if(flag){puts("-1");continue;}
        build();
        printf("%d\n",DP(1));
    }
    return 0;
}

//视频代码
// 树上倍增+虚树+树形DP 150ms
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=100005,M=N*2;
int h[N],to[M],ne[M],tot;
void add(int x,int y){ //连边
  to[++tot]=y;ne[tot]=h[x];h[x]=tot;
}
int dep[N],fa[N][20],siz[N];
int dfn[N],cnt; //dfs序
int s[N],top;   //栈
int n,k,q,a[N],ans;

void dfs(int x, int f){ //树上倍增
  dfn[x]=++cnt;
  dep[x]=dep[f]+1; fa[x][0]=f; siz[x]=1; 
  for(int i=1; i<=19; i++) 
    fa[x][i]=fa[fa[x][i-1]][i-1];
    
  for(int i=h[x]; i; i=ne[i]){
    int y=to[i];
    if(y==f) continue;
    dfs(y,x);
    siz[x]+=siz[y];
  }
}
int lca(int x, int y){ //求lca
  if(dep[x]<dep[y])swap(x, y);
  for(int i=19; ~i; i--)
    if(dep[fa[x][i]]>=dep[y])
      x=fa[x][i];
  if(x==y) return y;
  
  for(int i=19; ~i; i--)
    if(fa[x][i]!=fa[y][i])
      x=fa[x][i], y=fa[y][i];
  return fa[x][0];
}
int cmp(int a,int b){ 
  return dfn[a]<dfn[b];
}
void build(){ //建虚树
  sort(a+1,a+k+1,cmp); //按dfs序排序
  tot=0; //清空
  s[top=1]=1; //根节点入栈
  if(a[1]!=1) s[++top]=a[1];
  for(int i=2; i<=k; i++){ //枚举查询点
    int l=lca(s[top],a[i]);
    // 对当前链连边,top出栈
    while(top>1 && dep[s[top-1]]>=dep[l]) 
      add(s[top-1],s[top]), top--;
    // 对lca和top连边,top出栈,lca入栈
    if(l!=s[top]) add(l,s[top]), s[top]=l;
    // 查询点入栈
    s[++top]=a[i];
  }
  while(top) //对最后一条链连边,top出栈
    add(s[top-1],s[top]), top--;
}
void DP(int x){ //树形DP
  if(siz[x]){   //x是查询点
    for(int i=h[x]; i; i=ne[i]){
      DP(to[i]);
      if(siz[to[i]]) ans++, siz[to[i]]=0;
    }
  }
  else{ //x不是查询点
    for(int i=h[x]; i; i=ne[i]){
      DP(to[i]);
      siz[x]+=siz[to[i]], siz[to[i]]=0;
    }
    if(siz[x]>1) ans++, siz[x]=0;
  }
  h[x]=0; //清空
}
int main(){
  scanf("%d",&n);
  for(int i=1;i<n;i++){
    int x,y; scanf("%d%d",&x,&y);
    add(x,y); add(y,x);
  }
  dfs(1,0);
  memset(h+1,0,n<<2);
  memset(siz+1,0,n<<2); //清空
  scanf("%d",&q);
  while(q--){ 
    scanf("%d",&k);
    bool flag=0; siz[1]=0; //清空
    for(int i=1; i<=k; i++)
      scanf("%d",&a[i]),siz[a[i]]=1;
    for(int i=1; i<=k; i++)
      if(siz[fa[a[i]][0]]){ //无解
        while(k) siz[a[k--]]=0; //清空
        puts("-1"); flag=1; break;
      }
    if(flag) continue;
    build();
    ans=0; DP(1);
    printf("%d\n",ans);
  }
  return 0;
}