虚树入门

今天学了一下虚树，简单谈一下有什么用。

所谓虚树，其实就是把询问中需要用到的点建到另一棵树上，比如如果我们当前询问一条链上的两个端点，原本如果做dfs dp的话我们的复杂度是o(n)的，但是如果是虚树，那么树上就只会有这两个端点，两个端点之间的那条边记录了原本整条链上的信息。于是复杂度变成了o(2)的。

那么怎么建虚树呢？一般题中除了给出的询问点（之后成为关键点），我们还会用到关键点的lca（我不知道一般是lca还是一定是lca。），但是lca数也是o(n^2)的，于是我们想到把关键点按dfs序排序，比如设有三个点x,y,z,，他们按dfs序排序，lca(y,z)一定在lca(x,y)或者lca(y,z)中（其实本来想想也知道，一棵树上k个点的lca不管怎么组合应该是不超过k-1个的）。于是我们现在找到了2*k级别的点，问题是怎么把他们丢到一棵树上去。

我们先再次把所有点按dfs序排序，然后我们考虑这样一种方法，我们维护一个栈，如果栈为空，直接加点，否则我们看栈顶的点是不是当前点的祖先，如果不是，那么弹出栈顶继续，否则就可以把当前点加进栈了（然后从栈顶向这个点连一条边）。（因为之前插入的点可能是和当前点是并列关系，这个不一定会需要用到lca，因为我们记录一个dfs时入队和出队的顺序就可以了）。（第一个点就直接作为根了）。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <ctime>
#define inf (long long)100000000
using namespace std;
struct node {int to;int next;int len;
};node edge[500010],bian[2000010];
int in[200010],out[200010],dep[200010],f[200010][21],root;
int tim = 0,fir[200010],first[200010],n,a,b,m,Q,stack[200010];
int sum=0,size=0,len,top,list[200010],que[200010];
long long Dp[200010][3];
bool instack[200010],mark[200010];
bool comp(const int &x,const int &y) {return in[x] < in[y];}
bool check(int x,int y) {return in[x] <= in[y] && out[x] >= out[y];}
void add(int x,int y) {
 edge[ ++ sum].to = y;
 edge[sum].next = fir[x];
 fir[x] = sum;
}
void inser(int x,int y,int z) {
 bian[ ++ size].to = y;
 bian[size].next = first[x];
 first[x] = size;
 bian[size].len = z;
}
void dfs(int x,int depth,int Anc) {
 dep[x] = depth;
 f[x][0] = Anc;
 in[x] = ++ tim;
 for(int i = 1;i <= 20;i ++) 
     f[x][i] = f[f[x][i - 1]][i - 1];
 for(int u = fir[x];u;u = edge[u].next) 
     if(dep[edge[u].to] == 0)
         dfs(edge[u].to,depth + 1,x);
 out[x] = ++ tim;
} 
int lca(int x,int y) {
 if(dep[x] < dep[y]) swap(x,y);
 for(int i = 20;i >= 0;i --) 
  if(dep[f[x][i]] >= dep[y]) 
   x = f[x][i];
 if(x == y) return x;
 for(int i = 20;i >= 0;i --) 
     if(f[x][i] != f[y][i])
         x = f[x][i],y = f[y][i];
 return f[x][0];
}
int main() {
 scanf("%d",&n);
 for(int i = 1;i <= n - 1;i ++) {
  scanf("%d%d",&a,&b);
  add(a,b);
  add(b,a);
 }
 dfs(1,1,1);
 scanf("%d",&Q);
 while(Q --) {
  scanf("%d",&m);len = m;top = 0;root = 0;
  for(int i = 1;i <= m;i ++) scanf("%d",&list[i]),que[i] = list[i];
  sort(list + 1,list + m + 1,comp);
  for(int i = 1;i < m;i ++) 
      list[++ len] = lca(list[i],list[i + 1]);
  sort(list + 1,list + len + 1,comp);
  len = unique(list + 1,list + len + 1) - list - 1;
  for(int i = 1;i <= len;i ++) {
   while(top > 0 && !check(stack[top],list[i]))
       top --;
   if(stack[top] == 0) root = list[i];
   else {
    int s = stack[top],t = list[i];
    inser(s,t,dep[t] - dep[s]);
   }
   stack[ ++ top] = list[i];
  }
  for(int i = 1;i <= len;i ++) instack[list[i]] = true;
  for(int i = 1;i <= m;i ++) mark[que[i]] = true;
  //dp(root);
  for(int i = 1;i <= len;i ++) instack[list[i]] = false;
  for(int i = 1;i <= m;i ++) mark[que[i]] = false;
  for(int i = 1;i <= len;i ++) first[list[i]] = 0;size = 0;
 }
 return 0;
}