数据生成器

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int n, m, a[100001];
set< pair<int, int> > c;

inline void mkd() {
  printf("%d %d\n", n, m);
  for (int i = 1; i <= n; i++)
    a[i] = i;
  random_shuffle(a + 2, a + n + 1);
  int l = (rand() * rand()) % (n / 10) + 1;
  c.clear();
  for (int i = 2; i <= l; i++)
        printf("%d %d\n", a[1], a[i]), --m, c.insert(make_pair(1, i)), c.insert(make_pair(i, 1));

  for (int i = l + 1; i <= n; i++) {
    int x = (rand() * rand()) % (i - 1) + 1;
    printf("%d %d\n", a[x], a[i]);
    --m;
    c.insert(make_pair(x, i));
    c.insert(make_pair(i, x));
  }
  
  for (int i = 1; i <= m; i++) {
    int x = (rand() * rand()) % n + 1, y = (rand() * rand()) % n + 1;
    for (; x == y || c.find(make_pair(x, y)) != c.end();)
      x = (rand() * rand()) % n + 1, y = (rand() * rand()) % n + 1;
    c.insert(make_pair(x, y));
    c.insert(make_pair(y, x));
    printf("%d %d\n", a[x], a[y]);
  }
}

inline void mkd1() {
  printf("%d %d\n", n, m);
  for (int i = 1; i <= n; i++)
    a[i] = i;
  random_shuffle(a + 2, a + n + 1);
  c.clear();
  for (int i = 2; i <= n; i++)
    printf("%d %d\n", a[1], a[i]), --m, c.insert(make_pair(1, i)), c.insert(make_pair(i, 1));
  for (int i = 1; i <= m; i++) {
    int x = (rand() * rand()) % n + 1, y = (rand() * rand()) % n + 1;
    for (; x == y || c.find(make_pair(x, y)) != c.end();)
      x = (rand() * rand()) % n + 1, y = (rand() * rand()) % n + 1;
    c.insert(make_pair(x, y));
    c.insert(make_pair(y, x));
    printf("%d %d\n", x, y);
  }
}

int main() {
  n = 10; m = 19; freopen("starwar1.in", "w", stdout); mkd();
  n = 100; m = 200; freopen("starwar2.in", "w", stdout); mkd();
  n = 1000; m = 1100; freopen("starwar3.in", "w", stdout); mkd();
  n = 1000; m = 1100; freopen("starwar4.in", "w", stdout); mkd();
  n = 100000; m = n - 1; freopen("starwar5.in", "w", stdout); mkd();
  n = 100000; m = n - 1; freopen("starwar6.in", "w", stdout); mkd();
  n = 100000; m = n - 1; freopen("starwar7.in", "w", stdout); mkd();
  n = 100000; m = n; freopen("starwar8.in", "w", stdout); mkd();
  n = 100000; m = n; freopen("starwar9.in", "w", stdout); mkd();
  n = 100000; m = n; freopen("starwar10.in", "w", stdout); mkd();
  n = 100000; m = n + 10; freopen("starwar11.in", "w", stdout); mkd();
  n = 100000; m = n + 10; freopen("starwar12.in", "w", stdout); mkd();
  n = 100000; m = n + 10; freopen("starwar13.in", "w", stdout); mkd();
  n = 100000; m = n + 10; freopen("starwar14.in", "w", stdout); mkd();
  n = 100000; m = n + 100; freopen("starwar15.in", "w", stdout); mkd();
  n = 100000; m = n + 100; freopen("starwar16.in", "w", stdout); mkd();
  n = 100000; m = n + 100; freopen("starwar17.in", "w", stdout); mkd();
  n = 100000; m = n + 100; freopen("starwar18.in", "w", stdout); mkd();
  n = 100000; m = n + 100; freopen("starwar19.in", "w", stdout); mkd1();
  n = 100000; m = n + 100; freopen("starwar20.in", "w", stdout); mkd1();
  n = 100000; m = n + 100; freopen("starwar.in", "w", stdout); mkd();
}

首先求出所有特殊点，特殊点的定义是从 1 开始做一遍 bfs 后，拥有非树边的点。这样的特殊点最多有 200 个。

接着我们把这些特殊点到所有点的距离都算出来。

然后我们枚举把基地建立在哪个星球上，对于每个特殊点，我们都可以算出来通过这个特殊点黑暗势力与光明势力的分界点，分界点下面的子树归光明势力所有（注意特殊边连接的两个点的深度差最多是 1）。相当于我们有一些子树，要求出它们的并的大小，这个可以用 dfs 序列解决。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

struct node {
    node *next;
    int where;
} *first[200001], a[400001];

int n, m, l, dist[200001], c[200001], f[200001][21], size[200001], spe[200001], cnt, sd[301][200001], tot, L[200001],
    R[200001], w[10001], len;
bool b[200001];

inline void makelist(int x, int y) {
    a[++l].where = y;
    a[l].next = first[x];
    first[x] = &a[l];
}

int r[200001];

inline void dfs(int cur) {
    L[cur] = ++tot;
    for (node *x = first[cur]; x; x = x->next)
        if (f[x->where][0] == cur)
            dfs(x->where);
    R[cur] = tot;
}

int jump(int i, int t) {
    for (int step = 0; t; ++step, t >>= 1)
        if (t & 1)
            i = f[i][step];
    return i;
}

void calc(int i, int t) {
    if (dist[i] < t)
        return;
    i = jump(i, (dist[i] - t) / 2);
    w[++len] = i;
}

bool cmp(const int &x, const int &y) {
    return L[x] < L[y];
}

int main() {
    freopen("starwar.in", "r", stdin);
    freopen("starwar.out", "w", stdout);
    memset(first, 0, sizeof(first));
    l = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        makelist(x, y);
        makelist(y, x);
    }
    memset(f, 0, sizeof(f));
    memset(dist, 0, sizeof(dist));
    dist[1] = 1;
    c[1] = 1;
    for (int k = 1, l = 1; l <= k; l++) {
        int m = c[l];
        for (node *x = first[m]; x; x = x->next)
            if (!dist[x->where])
                dist[x->where] = dist[m] + 1,
                                 c[++k] = x->where,
                                          f[x->where][0] = m;
    }
    for (int i = n; i; --i) {
        int m = c[i];
        size[m] = 1;
        for (node *x = first[m]; x; x = x->next)
            if (f[x->where][0] == m)
                size[m] += size[x->where];
    }
    for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= n; j++)
            f[j][i] = f[f[j][i - 1]][i - 1];
    cnt = 0;
    for (int i = 1; i <= n; i++)
        for (node *x = first[i]; x; x = x->next)
            if (f[i][0] != x->where && f[x->where][0] != i) {
                spe[++cnt] = i;
                break;
            }

    memset(sd, 0, sizeof(sd));
    for (int i = 1; i <= cnt; i++) {
        sd[i][spe[i]] = 1;
        c[1] = spe[i];
        for (int k = 1, l = 1; l <= k; l++) {
            int m = c[l];
            for (node *x = first[m]; x; x = x->next)
                if (!sd[i][x->where])
                    sd[i][x->where] = sd[i][m] + 1,
                                      c[++k] = x->where;
        }
    }
    tot = 0;
    dfs(1);

    int ans = n;
    for (int i = 1; i <= n; i++) {
        if (i == 1)
            continue;
        len = 0;
        calc(i, 1);
        for (int j = 1; j <= cnt; j++)
            calc(spe[j], sd[j][i]);
        sort(w + 1, w + len + 1, cmp);
        int res = n;
        for (int Left = 1; Left <= len; ) {
            int j = Left;
            for (; Left <= len && L[w[Left]] >= L[w[j]] &&  L[w[Left]] <= R[w[j]]; ++Left);
            res -= size[w[j]];
        }
        ans = min(ans, res);
    }
    printf("%d\n", ans);
}