NC13950 Alliances

题目地址：

https://ac.nowcoder.com/acm/problem/13950

基本思路：

我们先对题进行分析，如果不考虑联盟，只对单一的帮派来说，我们找距离首都最近的一个帮派。
那么分情况讨论一下，如果首都不在这个帮派的 $lca$ 的子树里，那么最短距离很明显就是首都到这个帮派 $lca$ 的距离。
如果首都在这个帮派的 $lca$ 的子树里，那么我们只要在 $dfs$ 序里找最靠近这个首都的左右两个帮派取最小的距离就可以了。
然后我们思考引入了联盟的情况有什么区别，
首先如果首都不在联盟的 $lca$ 的子树里，那么情况和只有帮派时是一样的，只要找联盟 $lca$ 和首都的距离就行了。
然后是首都在联盟的 $lca$ 的子树中的情况，这个时候我们其实还有两种情况可以讨论，
一是首都所在这个点实际已经被控制的情况，这时也就是说首都的一个儿子或者首都自身被直接占领了，也就是说首都 $dfs$ 右边的第一个被直接占领城市和首都的 $lca$ 是首都本身的情况。
二这个点实际没有被控制的情况，这时的最短距离实际上就是对于每个帮派的情况，找首都和它们的最小距离，然后再总体取个最小就行了。因为这部分同样要找首都 $dfs$ 序左右被占领城市和首都的 $lca$ 到首都的距离，所以实际上一二两种情况可以合并。

$dfs$ 序里找最近的被占领城市的时候我们可以用二分优化，这样我们就能通过这题了。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 5e5 + 10;
int n;
struct edge {
    int next, v;
}edges[maxn << 1];
int cnt,tot;
int head[maxn];
void init() {
  memset(head, -1, sizeof(head));
  cnt = 0; tot = 0;
}
void add_edge(int u,int v) {
  edges[cnt].next = head[u];
  edges[cnt].v = v;
  head[u] = cnt++;
}
int dep[maxn],l[maxn],r[maxn],dfn[maxn];
int f[maxn][31];
void dfs(int u,int fa) {
  dep[u] = dep[fa] + 1;
  l[u] = ++tot; // 入栈;
  dfn[tot] = u;
  for (int i = 0; i <= 29; i++)
    f[u][i + 1] = f[f[u][i]][i];
  for (int i = head[u]; i != -1; i = edges[i].next) {
    int v = edges[i].v;
    if (v == fa)
      continue;
    f[v][0] = u;
    dfs(v, u);
  }
  r[u] = tot; //出栈;
}
int lca(int x,int y) {
  if (dep[x] < dep[y])
    swap(x, y);
  for (int i = 30; i >= 0; i--) {
    if (dep[f[x][i]] >= dep[y])
      x = f[x][i];
    if (x == y)
      return x;
  }
  for (int i = 30; i >= 0; i--) {
    if (f[x][i] != f[y][i]) {
      x = f[x][i];
      y = f[y][i];
    }
  }
  return f[x][0];
}
int dist(int a,int b) {
  return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}
vector<int> memo[maxn];
int LCA[maxn],a[maxn]; // 记录每个帮派的LCA;
signed main() {
  n = read();
  init();
  rep(i, 1, n - 1) {
    int u = read(), v = read();
    add_edge(u, v);
    add_edge(v, u);
  }
  dfs(1, 0);
  int k = read();
  rep(i,1,k) {
    int num = read();
    rep(j, 1, num) {
      int v = read();
      memo[i].push_back(l[v]);
      if (j == 1) LCA[i] = v;
      else LCA[i] = lca(LCA[i], v);
    }
    sort(memo[i].begin(), memo[i].end());
  }
  int q = read();
  while (q--){
    int cap = read(),num = read();
    int now = 0; // 联盟的LCA;
    rep(i,1,num){
      a[i] = read();
      if(i == 1) now = LCA[a[i]];
      else now = lca(now,LCA[a[i]]);
    }
    if(l[cap] < l[now] || l[cap] > r[now]){ // 首都不在联盟的子树里的情况;
      print(dist(cap,now));
    }else{
      int ans = INF;
      rep(i,1,num){
        auto it = lower_bound(memo[a[i]].begin(),memo[a[i]].end(),l[cap]);
        if(it != memo[a[i]].end()){ //找首都dfs序左边离最近的被占领城市;
          ans = min(ans,dist(cap,lca(cap,dfn[*it])));
        }
        if(it != memo[a[i]].begin()) {//找首都dfs序右边离最近的被占领城市;
          --it;
          ans = min(ans,dist(cap,lca(cap,dfn[*it])));
        }
      }
      print(ans);
    }
    puts("");
  }
  return 0;
}