【解题报告】联合省选 2021 A卷

本人被省选搞无语了，水平较低，若被叉请直接私信 $\text{D}$ 我（bushi）。

$\text{card}$

考虑二分答案。

设二分的极差为 $l$，枚举的最小值为 $x$，那么所有数字都要在 $[x,x+l]$ 之间。

把 $a,b$ 混在一起排序，双指针维护区间内出现了多少个 $a$，多少个 $b$，多少个 $a,b$ 都出现了。当所有位置的 $a,b$ 在区间中都至少出现了一个，区间才可能合法。

对于一个合法区间，区间内只出现了 $b$ 的那些需要翻，这等价于区间外有多少 $a$，前缀和后缀和维护即可。

时间复杂度 $\mathcal{O}(n\log n)$。

#include<bits/stdc++.h>
using namespace std;

#define FILE
//#define int long long
#define LL long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define fst first
#define scd second
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? -(x) : (x))

const int MAXN = 2e6 + 10;
const int INF = 2e9;
//const int mod = 998244353;
//const int mod = 1e9 + 7;

int n, m;
int a[MAXN], b[MAXN];
int pre[MAXN], suf[MAXN];
int buk[MAXN];

struct NODE {
    int x, opt;
    NODE(int _x = 0, int _o = 0) : x(_x), opt(_o) {}
    bool operator < (const NODE &b) const {return x < b.x;}
} s[MAXN];

template<typename T> inline void read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while('0' <= c && c <= '9') {a = (a * 10) + (c ^ 48); c = getchar();}
    a *= f;
}

bool chk(int add) {
    int p = 1, in = 0;
    for(int i = 1; i <= n; ++i) buk[i] = 0;
    for(int i = 1, to; i <= (n * 2); ++i) {
        while(p <= (n * 2) && s[p].x <= s[i].x + add) {
            to = s[p].opt; if(to > n) to -= n;
            if(!(buk[to]++)) in++;
            p++;
        }
        if(in == n && pre[i - 1] + suf[p] <= m) return true;
        to = s[i].opt; if(to > n) to -= n;
        if(!(--buk[to])) in--;
    }        
    return false;
}

signed main() {
#ifdef FILE
    freopen("card.in", "r", stdin);
    freopen("card.out", "w", stdout);
#endif
    read(n); read(m);
    for(int i = 1; i <= n; ++i) read(a[i]), s[i] = NODE(a[i], i);
    for(int i = 1; i <= n; ++i) read(b[i]), s[i + n] = NODE(b[i], i + n);
    sort(s + 1, s + (n * 2) + 1);
    for(int i = 1; i <= (n << 1); ++i) pre[i] = pre[i - 1] + (s[i].opt <= n);
    for(int i = (n << 1); i >= 1; --i) suf[i] = suf[i + 1] + (s[i].opt <= n);
    int L = 0, R = 1e9, mid;
    while(L < R) {
        mid = (L + R) >> 1;
        if(chk(mid)) R = mid;
        else L = mid + 1;
    }
    printf("%d\n", L);
    return 0;
}

$\text{matrix}$

首先考虑如果没有 $[0,{10}^6]$ 的限制要怎么做：可以随便构造，比如先令第一行第一列都是 $0$，然后从左上到右下依次推过来。

考虑如何调整到 $[0,{10}^6]$ 之内。如果需要一个位置 $(i,j)+1$，那么可以让第 $i$ 行 $+1,-1,+1,-1\cdots$ 交替进行，使得原本的方案修改后依旧合法。或者让第 $j$ 列进行这个操作，同样可以使得当前状态仍然合法。

不妨设 $p_i,q_j$ 分别表示第 $i$ 行、第 $j$ 列进行了多少次这样的操作，然后就会发现对于每一个点 $(i,j)$，若需要他在 $[0,{10}^6]$ 之内，那么就形如一个差分约束的形式了。

但是，有时候可能会出现 $x+y\le w$ 的形式，也就是两个未知数中间是加号，这是差分约束无法解决的。观察发现，这种情况当且仅当当前行、列都恰好是 $+1$ 或者 $-1$ 的时候会出现。

那么考虑调整一下 $p_i,q_j$ 加数的方法，可以这样分配加减：

对于行的操作：

$$\left[\begin{array}{c}+-+-+\\ -+-+-\\ +-+-+\\ -+-+-\\ +-+-+\end{array}\right]$$

对于列的操作：

$$\left[\begin{array}{c}-+-+-\\ +-+-+\\ -+-+-\\ +-+-+\\ -+-+-\end{array}\right]$$

这样之后同一个点的 $p_i,q_j$ 就都是差分的形式了，直接上差分约束就可以了。本题图十分稠密，用 $\text{SPFA}$ 还不如 $\text{Bellman-Ford}$ 快。

//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 610;
const int MAXM = 5e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int T, n, m;
int a[MAXN][MAXN], b[MAXN][MAXN];
int dis[MAXN], cnt[MAXN], w[MAXN][MAXN];
bool inq[MAXN];
queue<int> Q;

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}

void add(int a, int b, int v) {
    w[a][b] = v, w[b][a] = (int)1e6 - v;
}

bool BellmanFord() {
    memset(cnt, 0, sizeof cnt);
    for(int i = 1; i <= n + m; ++i)
        dis[i] = 0, inq[i] = true;
    for(int t = 1; t <= n + m + 1; ++t) {
        bool flag = false;
        for(int i = 1, l, r; i <= n + m; ++i) {
            if(i <= n) l = n + 1, r = n + m;
            else l = 1, r = n;
            for(int j = l; j <= r; ++j)
                if(dis[j] > dis[i] + w[i][j])
                    dis[j] = dis[i] + w[i][j], flag = true;
        }
        if(!flag) break;
        if(t == n + m + 1) return false;
    }
    return true;
}

void solve() {
    read(n), read(m); memset(w, 0, sizeof w);
    for(int i = 1; i < n; ++i)
        for(int j = 1; j < m; ++j)
            read(b[i][j]);
    for(int i = 1; i <= n; ++i) a[i][1] = 0;
    for(int i = 1; i <= m; ++i) a[1][i] = 0;
    for(int i = 2; i <= n; ++i)
        for(int j = 2; j <= m; ++j)
            a[i][j] = b[i - 1][j - 1] - a[i - 1][j] - a[i - 1][j - 1] - a[i][j - 1];
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if((i + j) & 1) add(j + n, i, a[i][j]);
            else add(i, j + n, a[i][j]);
        }
    }
    if(!BellmanFord()) return puts("NO"), void();
    puts("YES");
    for(int i = 1; i <= n; ++i) {
        for(int j = 1, opt; j <= m; ++j) {
            opt = ((i + j) & 1) ? -1 : 1;
            printf("%lld ", a[i][j] + (dis[i] - dis[j + n]) * opt);
        }
        putchar('\n');
    }
}

signed main () {
#ifdef FILE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    read(T);
    while(T--) solve();
    return 0;
}

$\text{graph}$

发现若在 $f(u,G)$ 中，$u$，$v$ 有贡献，当且仅当：

• 存在一条从 $u$ 到 $v$，且路径上点标号均不小于 $v$ 的路径。
• 存在一条从 $v$ 到 $u$，且路径上点标号均不小于 $v$ 的路径。

两个东西对称，讨论一个即可。

先讨论第二个条件。可以枚举 $v$，然后考虑倒序加边，看要加到什么时候，一对 $u,v$ 才会存在合法的路径。对于一条边 $x\to y$，显然只有 $y$ 一侧的联通块中有贡献，那么对于起始点 $v$，且当前已经存在从 $v$ 到 $x$ 的合法路径，那么就可以更新 $y$ 可以到的位置。可以发现，由于每一对 $u,v$ 都只会记录使其合法的最大编号的边，所以对于一个固定的 $v$，整张图只会被遍历一次。

第一个条件，只需要把边反过来建即可。最后只需要计算出倒序加入每一条边之后，新增加了多少合法点对，做一个后缀和就行。时间复杂度 $\mathcal{O}(nm)$，民间数据卡常。

//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
//#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 1e3 + 10;
const int MAXM = 2e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

struct EDGE {
    int head[MAXN], siz;
    int nxt[MAXM], to[MAXM];
    inline void add(int x, int y) {
        nxt[++siz] = head[x];
        to[siz] = y, head[x] = siz;
    }
} e[2];

int n, m;
int X[MAXM], Y[MAXM];
int val[2][MAXN][MAXN];
int Ans[MAXM];

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}

void DFS(int opt, int x, int st, int v) {
    val[opt][st][x] = v;
    for(int &i = e[opt].head[x], to; i; i = e[opt].nxt[i]) {
        to = e[opt].to[i];
        if(to < st || val[opt][st][to] != m + 2) continue;
        DFS(opt, to, st, v);
    }
}

signed main () {
#ifdef FILE
    freopen("graph.in", "r", stdin);
    freopen("graph.out", "w", stdout);
#endif
    read(n), read(m);
    for(int i = 1; i <= m; ++i) read(X[i]), read(Y[i]);
    for(int i = 1; i <= n; ++i) {
        for(int j = i; j <= n; ++j) val[0][i][j] = val[1][i][j] = m + 2;
        val[0][i][i] = val[1][i][i] = m + 1, e[0].siz = e[1].siz = 0;
        for(int j = i; j <= n; ++j) e[0].head[j] = e[1].head[j] = 0;
        for(int j = m; j >= 1; --j) {
            if(X[j] < i || Y[j] < i) continue;
            e[0].add(X[j], Y[j]), e[1].add(Y[j], X[j]);
            if(val[0][i][X[j]] != m + 2 && val[0][i][Y[j]] == m + 2)
                DFS(0, Y[j], i, j);
            if(val[1][i][Y[j]] != m + 2 && val[1][i][X[j]] == m + 2)
                DFS(1, X[j], i, j);
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = i; j <= n; ++j)
            if(max(val[0][i][j], val[1][i][j]) < m + 2)
                Ans[min(val[0][i][j], val[1][i][j])]++;
    for(int i = m; i >= 1; --i) Ans[i] += Ans[i + 1];
    for(int i = 1; i <= m + 1; ++i) printf("%d ", Ans[i]);
    return 0;
}

$\text{gem}$

套路地把路径按 $\text{lca}$ 拆开，把权值按照 $P$ 中顺序重新编号。

先考虑从 $s$ 到 $\text{lca}$ 的部分，设 $f_x$ 为当前节点向上的最近的，编号为 $x$ 的点。然后就可以倍增了，这里是一个 $\log$。

那么现在所有询问都到了 $\text{lca}$，考虑到 $t$ 的路径中可以到哪里。显然这个东西是单调的，所以可以二分。二分一个询问的答案，然后从 $t$ 同样维护类似的倍增数组，检查一下能不能接上就行。

考场脑抽了写了主席树但是懒得重新写了就这样吧

貌似可以用点分治什么的做到一个 $\log$，但这个做法是 $\mathcal{O}\mathcal{(}\mathcal{n}\log \mathcal{n}\mathcal{+}\mathcal{q}{\log }^{\mathcal{2}}\mathcal{n}\mathcal{)}$。

#include<bits/stdc++.h>
using namespace std;

//#define FILE
//#define int long long
#define LL long long
#define vec vector
#define pii pair<int, int>
#define fst first
#define scd second
#define pb push_back
#define abs(x) ((x) < 0 ? -(x) : (x))

const int MAXN = 2e5 + 10;
const int MAXM = 5e4 + 10;
const int INF = 2e9;
//const int mod = 998244353;
//const int mod = 1e9 + 7;

struct EDGE {
    int head[MAXN], siz;
    int nxt[MAXN << 1], to[MAXN << 1];
    inline void add(int x, int y) {
        nxt[++siz] = head[x];
        to[siz] = y; head[x] = siz;
    }
} e;

struct Query {
    int lca, id;
    Query(int _lca = 0, int _id = 0) : lca(_lca), id(_id) {}
};

int n, m, c, q;
int P[MAXM], w[MAXN], fa[MAXN], dep[MAXN];
int dfn[MAXN], dfnc, top[MAXN], p[MAXN][21];
int nxt[MAXN][21], num[MAXM];
int sum[MAXN * 30], ls[MAXN * 30], rs[MAXN * 30], cnt, root[MAXN];
int ss[MAXN], tt[MAXN], Ans[MAXN];
bool vis[MAXN];
vec<Query> qs[MAXN];

template<typename T> inline void read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while('0' <= c && c <= '9') {a = (a * 10) + (c ^ 48); c = getchar();}
    a *= f;
}

void DFS(int x, int f) {
    fa[x] = f;
    p[x][0] = f, dep[x] = dep[f] + 1;
    for(int i = 1; i < 20; ++i)
        p[x][i] = p[p[x][i - 1]][i - 1];
    for(int i = e.head[x], to; i; i = e.nxt[i]) {
        to = e.to[i];
        if(to == f) continue;
        DFS(to, x);
    }
}

int LCA(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 19; ~i; --i)
        if(dep[p[x][i]] >= dep[y]) x = p[x][i];
    if(x == y) return x;
    for(int i = 19; ~i; --i)
        if(p[x][i] ^ p[y][i]) x = p[x][i], y = p[y][i];
    return p[x][0];
}

void trans() {
    static int id[MAXM];
    for(int i = 1; i <= c; ++i) id[P[i]] = i, P[i] = i;
    for(int i = 1; i <= n; ++i) w[i] = id[w[i]];
}

void calc1(int x) {
    int sav = num[w[x]];
    if(w[x]) {
        num[w[x]] = x;
        nxt[x][0] = num[w[x] + 1];
        for(int i = 1; i < 20; ++i)
            nxt[x][i] = nxt[nxt[x][i - 1]][i - 1];
    }
    if(qs[x].size()) {
        for(int i = 0; i < qs[x].size(); ++i) {
            int s = num[1];
            if(dep[s] < dep[qs[x][i].lca]) continue;
            for(int j = 19; ~j; --j)
                if(dep[nxt[s][j]] >= dep[qs[x][i].lca]) s = nxt[s][j];
            Ans[qs[x][i].id] = w[s];
        }
        qs[x].clear();
    }
    for(int i = e.head[x], to; i; i = e.nxt[i]) {
        to = e.to[i];
        if(to == fa[x]) continue;
        calc1(to);
    }
    num[w[x]] = sav;
}

void add(int &x, int pre, int l, int r, int p, int v) {
    if(p < l || p > r) return;
    x = ++cnt;
    sum[x] = sum[pre], ls[x] = ls[pre], rs[x] = rs[pre];
    sum[x] += v;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(p <= mid) add(ls[x], ls[pre], l, mid, p, v);
    else add(rs[x], rs[pre], mid + 1, r, p, v);
}

int kth(int a, int b, int l, int r, int k) {
    if(sum[a] - sum[b] < k) return -1;
    if(l == r) return l;
    int mid = (l + r) >> 1, v = sum[ls[a]] - sum[ls[b]];
    if(k <= v) return kth(ls[a], ls[b], l, mid, k);
    else return kth(rs[a], rs[b], mid + 1, r, k - v);
}

void solve(int ii, int x) {
    static int lca, lim, l, r, mid, st, j;
    lca = qs[x][ii].lca;
    lim = Ans[qs[x][ii].id];
    l = 1, r = sum[root[x]] - sum[root[lca]];
    if(l > r) return;
    while(l < r) {
        mid = (l + r + 1) >> 1;
        st = num[kth(root[x], root[lca], 1, c, mid)];
        for(j = 19; ~j; --j)
            if(dep[nxt[st][j]] >= dep[lca]) st = nxt[st][j];
        if(w[st] <= lim + 1) l = mid;
        else r = mid - 1;
    }
    st = num[kth(root[x], root[lca], 1, c, l)];
    for(j = 19; ~j; --j)
        if(dep[nxt[st][j]] >= dep[lca]) st = nxt[st][j];
    if(w[st] <= lim + 1)
        Ans[qs[x][ii].id] = max(Ans[qs[x][ii].id], kth(root[x], root[lca], 1, c, l));
}

void calc2(int x) {
    if(w[x]) add(root[x], root[fa[x]], 1, c, w[x], 1);
    else root[x] = root[fa[x]];
    int sav = num[w[x]];
    if(w[x]) {
        num[w[x]] = x;
        nxt[x][0] = num[w[x] - 1];
        for(int i = 1; i < 20; ++i)
            nxt[x][i] = nxt[nxt[x][i - 1]][i - 1];
    }
    for(int ii = 0, j; ii < qs[x].size(); ++ii) solve(ii, x);
    for(int i = e.head[x]; i; i = e.nxt[i])
        if(e.to[i] != fa[x]) calc2(e.to[i]);
    num[w[x]] = sav;
}

signed main() {
#ifdef FILE
    freopen("gem.in", "r", stdin);
    freopen("gem.out", "w", stdout);
#endif
    read(n), read(m), read(c);
    for(int i = 1; i <= c; ++i) read(P[i]);
    for(int i = 1; i <= n; ++i) read(w[i]);
    trans();
    for(int i = 1, x, y; i < n; ++i) {
        read(x), read(y);
        e.add(x, y), e.add(y, x);
    }
    DFS(1, 0); read(q);
    for(int i = 1; i <= q; ++i) {
        read(ss[i]), read(tt[i]);
        qs[ss[i]].pb(Query(LCA(ss[i], tt[i]), i));
    }
    calc1(1);
    memset(nxt, 0, sizeof nxt), memset(num, 0, sizeof num);
    for(int i = 1; i <= n; ++i) qs[i].clear();
    for(int i = 1; i <= q; ++i)
        qs[tt[i]].pb(Query(LCA(ss[i], tt[i]), i));
    calc2(1);
    for(int i = 1; i <= q; ++i) printf("%d\n", Ans[i]);
    return 0;
}

$\text{ranklist}$

被题面送退役了的题......就 $\text{nm}$ 毁一生。

考虑 $\mathcal{O}(n!n)$ 的做法，直接暴力枚举一个顺序，然后贪心地做，尽量少地放 $b$ 即可。

套路地用状压 $\text{dp}$ 优化这个东西，一个 $\text{naive}$ 的想法是设 ${\text{dp}}_{S,i,x,y}$ 表示已经填了 $S$ 集合中的数，当前榜首为 $i$，$b_i=x$，当前 $b$ 的和为 $y$ 的时候的方案数。这个转移要 $\mathcal{O}(2^n{n}^2{m}^2)$，可能还没有上面那个暴力快。

考虑优化，观察到 $b$ 是单调不降的，这引导我们进行差分。差分之后，我们实际上就不需要知道上一个数的 $b$ 的实际值，只需要考虑当前的 $b$ 要比上一个 $b$ 大多少即可。那么先考虑省略一维 $x$，设 ${\text{dp}}_{S,i,y}$ 为上述状态删掉 $b_i=x$ 这个限制之后的状态。

那么当前只需要枚举一下前驱状态中，$\sum b$ 的值，然后贪心地加尽量少的 $b$ 即可。但是由于我们仍然需要判断 $\sum b\le m$，所以要类似提前计算贡献，把后面那些还没有填上的位置都加上当前的 $\mathrm{\Delta }b$。这样就可以 $\mathcal{O}(2^n{n}^{2}m)$，可以通过。

不知道考场上脑子里是装了什么搞得连题都没看懂，活该退役

//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 14;
const int MAXM = 510;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int n, m, Ans, maxp;
int a[MAXN], popc[(1 << (MAXN - 1)) + 10], p2[MAXN];
int dp[(1 << (MAXN - 1)) + 10][MAXN][MAXM];

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}

signed main () {
#ifdef FILE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    read(n), read(m); p2[0] = 1;
    for(int i = 1; i <= n; ++i) p2[i] = p2[i - 1] << 1;
    for(int i = 1; i <= n; ++i) read(a[i]);
    maxp = max_element(a + 1, a + n + 1) - a;
    for(int i = 1; i < p2[n]; ++i) popc[i] = popc[i >> 1] + (i & 1);
    for(int i = 1; i <= n; ++i) {
        if(n * (a[maxp] - a[i] + (i > maxp)) > m) continue;
        dp[1 << (i - 1)][i][(a[maxp] - a[i] + (i > maxp)) * n] = 1;
    }
    for(int S = 1; S < p2[n]; ++S) {
        for(int y = 1; y <= n; ++y) {
            if((S & p2[y - 1]) == 0) continue;
            for(int x = 1, nxt; x <= n; ++x) {
                if(S & p2[x - 1]) continue;
                nxt = S | p2[x - 1];
                for(int pre = 0, add; pre <= m; ++pre) {
                    add = max(a[y] - a[x] + (x > y), 0ll);
                    if(pre + add * (n - popc[S]) > m) break;
                    dp[nxt][x][pre + add * (n - popc[S])] += dp[S][y][pre];
                }
            }
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= m; ++j)
            Ans += dp[p2[n] - 1][i][j];
    printf("%lld\n", Ans);
    return 0;
}

$\text{dominator}$

先考虑建立支配树，那么一个点的受支配集就是支配树上的所有祖先。由于本题范围很小，所以可以考虑 $\mathcal{O}(n^2)$ 建支配树：

由于一开始 $1$ 可以到所有点，所以可以删除每一个点，求出 $1$ 不再能到的那些点，这些点被删除的点支配。接着记录每一个点被多少点支配了，用类似拓扑排序的方式，将点依次入队，然后把他所支配的点的计数器减一。若他支配的点的计数器被减后为 $1$，那么当前点就是这个被支配的点的父亲，接着把这个被支配的点入队即可。

分类讨论 考虑一个询问 $(s,t)$，若在支配树上是返祖边或重边，那么显然不会有任何用处。

若 $(s,t)$ 是前向边，也就是从祖先到后代，那么：找到 $s$ 的一个儿子 $x$，使得 $t$ 在 $x$ 的子树中。那么受支配集会改变的点是：

从 $t$ 出发，走原图的边且不经过 $x$，所能达到的所有在支配树上在 $x$ 子树内的点。

有以下的结论：

若 $t$ 指向一个点 $v$，使得 $v$ 不在 $x$ 的子树内，那么 $v$ 的受支配集不改变。

若 $v$ 是 $x$ 的祖先，其受支配集显然不会改变。若 $v$ 不是 $x$ 的祖先，那么 $v$ 一定是 $\text{LCA}(x,v)$ 的儿子，因为如果是 $\text{LCA}(x,v)$ 的孙子或更深的子孙，那么 $v$ 的父亲就不一定需要被经过了，这不符合支配树的定义。而 $v$ 是 $\text{LCA}(x,v)$ 的儿子的话，其受支配集同样不会改变——因为这条路径同样需要经过 $\text{LCA}(x,v)$。

那么，只要我不经过 $x$，且在 $x$ 的子树内，那么就一定出现了一条路径，使得可以不经过 $x$。这样其受支配集就减小了。

若 $(s,t)$ 是横叉边，那么询问等价于 $(\text{LCA}(s,t),t)$，这就转化为了前向边的情况。

若我通过 $(s,t)$ 这条边，那么相当于我没有经过 $\text{LCA}(s,t)$ 以下，到 $\text{fa}(t)$ 的所有点，而是经过了 $\text{LCA}(s,t)$ 到 $s$ 这段路径。而经过这段新路径，也不可能使得一个点的受支配集加入这条路径中的任何点，因为显然加边不会增大任何点的支配集。

因此，这条路径的贡献等价于 $(\text{LCA}(s,t),t)$ 的贡献——都是跳过了 $t$ 的一些祖先，因此转化不会有问题。

时间复杂度 $\mathcal{O}(nq)$。

//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
//#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 3010;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

struct EDGE {
    int head[MAXN], siz;
    int nxt[MAXN << 1], to[MAXN << 1];
    inline void add(int x, int y) {
        nxt[++siz] = head[x];
        to[siz] = y, head[x] = siz;
    }
} e, T;

int n, m, q, Ans;
int fa[MAXN], dep[MAXN], dfn[MAXN], siz[MAXN], dfnc;
int dom[MAXN][MAXN];
bool vis[MAXN];
queue<int> Q;

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}

void build() {
    static int cnt[MAXN];
    for(int i = 1; i <= n; ++i)
        dom[1][i] = dom[i][i] = true;
    for(int ban = 2; ban <= n; ++ban) {
        memset(vis, 0, sizeof(bool) * (n + 2));
        Q.push(1);
        while(Q.size()) {
            int x = Q.front(); Q.pop();
            if(x == ban || vis[x]) continue;
            vis[x] = true;
            for(int i = e.head[x], to; i; i = e.nxt[i]) {
                to = e.to[i];
                if(to == ban || vis[to]) continue;
                Q.push(to);
            }
        }
        for(int i = 1; i <= n; ++i) 
            if(!vis[i]) dom[ban][i] = true;
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(dom[i][j]) cnt[j]++;
    Q.push(1);
    while(Q.size()) {
        int x = Q.front(); Q.pop();
        for(int i = 1; i <= n; ++i) {
            if(!dom[x][i]) continue;
            if((--cnt[i]) == 1) T.add(x, i), Q.push(i);
        }
    }
}

void DFS(int x, int f) {
    dfn[x] = ++dfnc, fa[x] = f, dep[x] = dep[f] + 1, siz[x] = 1;
    for(int i = T.head[x], to; i; i = T.nxt[i]) {
        to = T.to[i];
        if(to == f) continue;
        DFS(to, x); siz[x] += siz[to];
    }
}

bool isanc(int x, int y) {
    while(y) {
        if(x == y) return true;
        y = fa[y];
    }
    return false;
}

int LCA(int x, int y) {
    while(x ^ y) {
        if(dep[x] < dep[y]) swap(x, y);
        x = fa[x];
    }
    return x;
}

void calc(int x, int ban) {
    if(vis[x] || ban == x) return;
    vis[x] = true;
    if(dfn[ban] <= dfn[x] && dfn[x] <= dfn[ban] + siz[ban] - 1) Ans++;
    for(int i = e.head[x], to; i; i = e.nxt[i]) {
        to = e.to[i];
        calc(to, ban);
    }
}

void solve() {
    int s, t; read(s), read(t);
    if(isanc(t, s)) return puts("0"), void();
    if(!isanc(s, t)) s = LCA(s, t);
    if(fa[t] == s) return puts("0"), void();
    int ban = t; while(fa[ban] ^ s) ban = fa[ban];
    memset(vis, 0, sizeof(bool) * (n + 2));
    Ans = 0; calc(t, ban);
    printf("%d\n", Ans);
}

signed main () {
#ifdef FILE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    read(n), read(m), read(q);
    for(int i = 1, x, y; i <= m; ++i) {
        read(x), read(y);
        e.add(x, y);
    }
    build(); DFS(1, 0);
    while(q--) solve();
    return 0;
}