没有传送门题目大意考场上的思路思路Hall 定理继续怎么做呢？参考代码
没有传送门
题目大意
给你一棵
n
n
个结点的数，每个结点有一种特产，用 aiai 表示。总共有
m
m
种特产。有 qq 个询问，每个询问形如：有
c
c
个人，分别在某些城市，现在他们要走到 LCA 处。他们能够买沿途的特产，要求：
每种特产要买只能买一件；
每个人买的特产数量要相等；
所有人买的特产都不能重复。
求最多能买多少种（件）特产。
n≤3×105n≤3×105，
q≤5×104
q
≤
5
×
10
4
，
m≤103
m
≤
10
3
，
c≤5
c
≤
5
。
Limited Constraint：
n≤3000
n
≤
3000
，
q≤3000
q
≤
3000
。
考场上的思路
考虑做 Limited Constraint。求 LCA 无话可说，
O(nlogn)
O
(
n
log
n
)
倍增即可。每个询问暴力往上走，记录出现了哪些特产，现在的问题是如何求答案。
考虑网络流。把每种特产看作一个点，向汇点连一条容量为
1
1
的边，把每个人看成一个点，向能够买的特产连一条容量为 11 的边。不能够直接求最大流，考虑二分答案。如果二分答案后求最大流满流，说明可行，否则需要减少答案。
使用 Dinic 进行求解，可以认为每次求解的时间复杂度为
O(n+m)
O
(
n
+
m
)
（我口胡的，不过你可以认为多路增广速度不错）。极限数据（两条链，所有特产都出现）要跑大约 3 sec，但出题人良心，直接让我过了 QAQ。
也想过树链剖分，但是感觉没卵用。
思路
考虑树链剖分 QAQ，不管怎么说把每个人能买的特产求出来再说。由于
m
m
比较小，又必须具体地求出每个人能买的特产种类（不然接下来怎么做 QAQ），因此考虑 bitset。
直接用树链剖分 线段树 bitset 的时间复杂度是 O(mωlog2n)O(mωlog2n) 的，算起来快
10000
10000
了，不太可过。考虑用预处理优化一下。预处理出每个结点到链顶的 bitset，查询时除了最后一段，其它的都直接用预处理后的值。预处理的时间复杂度是
O(nmω)
O
(
n
m
ω
)
的，单词查询的时间复杂度是
O(mωlogn)
O
(
m
ω
log
n
)
的。
（这里提醒一下，虽然
nm
n
m
看上去蛮大的，但是
mω
m
ω
蛮小的。取
ω=32
ω
=
32
时，你可以认为它的大小仅为
32
32
）
不考虑接下来怎么做，目前我们能够在
O(qmωlogn)
O
(
q
m
ω
log
n
)
的时间复杂度内求出每个人能买的特产，很优秀了。
接下来不要用网络流了，要用一个叫做 Hall 定理的东西。
Hall 定理
完全没有听说过啊 QAQ。
Hall 定理是跟二分图完美匹配有关的东西，先来一个定义：
完美匹配：若一个二分图的最大匹配数为
min(|X|,|Y|)
min
(
|
X
|
,
|
Y
|
)
，则称该二分图存在完美匹配。
Hall 定理：
二分图存在完美匹配当且仅当
X
X
中的任意 kk 个点至少与
Y
Y
中 kk 点有连边。
唉，我也不想学习怎么证明了，这里是王师傅的证明。一年前王师傅在我还在玩泥巴的时候就会了，太强辣！
继续怎么做呢？
直接把之前的网络流图搬过来肯定不行啊，那个不是匹配。不过考虑一个很笨的方法：如果之前我们不是通过修改源点到人的容量，而是加点呢？虽然在网络流中这个做法很傻，但是在不用网络流的这里就很聪明了——这个做法保证了求的东西是二分图的最大匹配。显然的是，如果一个答案合法，那么这个二分图就有完美匹配，也就是说任意
k
k
个点都至少能买 kk 个特产（有买
k
k
个特产的机会）。
对于同一个人来说，根本不用检查都属于他的点：只要这个人能买 kk 个特产，把他拆成
k
k
个点他还是能买 kk 个特产。所以问题就在于不同的人身上。我们把不同的人组合起来，分别检查是否满足霍尔定理即可。检查的时间复杂度为
O(2cmω)
O
(
2
c
m
ω
)
。
由于要满足霍尔定理，因此
ans×|S|≥check
a
n
s
×
|
S
|
≥
c
h
e
c
k
，所以答案为检查值
check
c
h
e
c
k
除以人数的下取整的最小值（因为要任意）。
参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::
cin;
using std::
cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
INT_PUT a =
0;
bool positive =
true;
char ch = getchar();
while (!(ch ==
'-' ||
std::
isdigit(ch))) ch = getchar();
if (ch ==
'-') { positive =
false; ch = getchar(); }
while (
std::
isdigit(ch)) { a = a *
10 - (ch -
'0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[
20];
int length =
0;
if (x <
0)
putchar(
'-');
else x = -x;
do buffer[length++] = -(x %
10) +
'0';
while (x /=
10);
do putchar(buffer[--length]);
while (length);
putchar(
'\n');
}
const int INF = (~(
int(
1) << (
sizeof(
int) *
8 -
1))) >>
1;
const int maxn =
int(
3e5) +
5;
const int maxm =
int(
1e3) +
5;
int n, m, q;
int a[maxn];
int LCA(
int,
int);
struct Query
{
int c[
6];
int lca;
void read()
{
c[
0] = readIn();
for (
int i =
1; i <= c[
0]; i++)
c[i] = readIn();
lca = LCA(c[
1], c[
2]);
for (
int i =
3; i <= c[
0]; i++)
lca = LCA(lca, c[i]);
}
} querys[maxn];
typedef std::
vector<std::vector<int> > Graph;
Graph G;
int parent[maxn];
int depth[maxn];
int size[maxn];
int heavy[maxn];
void DFS1(
int node)
{
depth[node] = depth[parent[node]] +
1;
size[node] =
1;
for (
int i =
0; i < G[node].size(); i++)
{
int to = G[node][i];
DFS1(to);
size[node] += size[to];
if (!heavy[node] || size[to] > size[heavy[node]])
heavy[node] = to;
}
}
int stamp;
int dfn[maxn];
int seq[maxn];
int top[maxn];
void DFS2(
int node,
int t)
{
stamp++;
dfn[node] = stamp;
seq[stamp] = node;
if (!t)
t = node;
top[node] = t;
if (heavy[node])
DFS2(heavy[node], t);
for (
int i =
0; i < G[node].size(); i++)
{
int to = G[node][i];
if (to == heavy[node])
continue;
DFS2(to,
0);
}
}
int LCA(
int u,
int v)
{
while (top[u] != top[v])
{
if (depth[top[u]] < depth[top[v]])
std::swap(u, v);
u = parent[top[u]];
}
return depth[u] < depth[v] ? u : v;
}
#define RunInstance(x) delete new x
struct brute
{
int stamp;
int vis[maxm];
int appear[
6][maxm];
struct NetworkFlow
{
struct Edge
{
int from, to, cap, flow;
Edge() {}
Edge(
int from,
int to,
int cap) : from(from), to(to), cap(cap), flow() {}
};
Graph G;
std::
vector<Edge> edges;
int addEdge(
int from,
int to,
int cap)
{
edges.push_back(Edge(from, to, cap));
edges.push_back(Edge(to, from,
0));
int i = edges.size();
G[from].push_back(i -
2);
G[to].push_back(i -
1);
return i -
2;
}
void operator=(
const NetworkFlow& b)
{
G = b.G;
edges = b.edges;
s = b.s;
t = b.t;
}
int s, t;
int level[maxn];
std::
vector<int> cur;
int Dinic(
int node,
int opt)
{
if (node == t || !opt)
return opt;
int flow =
0;
for (
int& i = cur[node]; i < G[node].size(); i++)
{
int t;
Edge& e = edges[G[node][i]];
if (e.flow < e.cap && level[node] +
1 == level[e.to] &&
(t = Dinic(e.to,
std::min(opt, e.cap - e.flow))))
{
flow += t;
opt -= t;
e.flow += t;
edges[G[node][i] ^
1].flow -= t;
if (!opt)
break;
}
}
return flow;
}
struct Queue
{
int c[maxn];
int head, tail;
Queue() : head(), tail() {}
void clear() { head = tail =
0; }
void push(
int x) { c[tail++] = x; }
void pop() { head++; }
int front() {
return c[head]; }
bool empty() {
return head == tail; }
} q;
int stamp;
int vis[maxn];
NetworkFlow() : stamp(), vis() {}
bool BFS()
{
q.clear();
stamp++;
vis[s] = stamp;
q.push(s);
level[s] =
0;
while (!q.empty())
{
int from = q.front();
q.pop();
for (
int i =
0; i < G[from].size(); i++)
{
const Edge
& e = edges[G[from][i]];
if (e.flow < e.cap && vis[e.to] != stamp)
{
vis[e.to] = stamp;
level[e.to] = level[from] +
1;
q.push(e.to);
}
}
}
return vis[t] == stamp;
}
int maxflow()
{
int flow =
0;
while (BFS())
{
cur.clear();
cur.resize(G.size());
flow += Dinic(s, INF);
}
return flow;
}
} nf, backup;
brute() : stamp(), vis(), appear()
{
backup.G.resize(m +
7);
backup.s =
0;
backup.t = m +
1;
for (
int i =
1; i <= m; i++)
backup.addEdge(i, backup.t,
1);
for (
int i =
1; i <= q; i++)
{
const int* c = querys[i].c;
int lca = querys[i].lca;
for (
int j =
1; j <= c[
0]; j++)
{
stamp++;
appear[j][
0] =
0;
int cnt = c[j];
while (
true)
{
if (vis[a[cnt]] != stamp)
{
vis[a[cnt]] = stamp;
appear[j][++appear[j][
0]] = a[cnt];
}
if (cnt == lca)
break;
cnt = parent[cnt];
}
}
int l =
0, r = m / c[
0] +
1;
while (r - l >
1)
{
int mid = (l + r) >>
1;
nf = backup;
for (
int j =
1; j <= c[
0]; j++)
for (
int k = appear[j][
0]; k; k--)
nf.addEdge(m +
1 + j, appear[j][k],
1);
for (
int j =
1; j <= c[
0]; j++)
nf.addEdge(nf.s, m +
1 + j, mid);
if (nf.maxflow() == mid * c[
0])
l = mid;
else
r = mid;
}
printOut(l * c[
0]);
}
}
};
struct work
{
typedef std::
bitset<1024> bitset;
class SegTree
{
static inline int code(
int l,
int r)
{
return (l + r) | (l != r);
}
bitset nodes[maxn *
2];
int g_L, g_R;
bitset query_(
int l,
int r)
{
if (g_L <= l && r <= g_R)
{
return nodes[code(l, r)];
}
int mid = (l + r) >>
1;
bitset ret;
if (g_L <= mid) ret |= query_(l, mid);
if (g_R > mid) ret |= query_(mid +
1, r);
return ret;
}
public:
SegTree() { build(
1, n); }
void build(
int l,
int r)
{
if (l == r)
{
nodes[code(l, r)].
set(a[seq[l]]);
return;
}
int mid = (l + r) >>
1;
build(l, mid);
build(mid +
1, r);
nodes[code(l, r)] = nodes[code(l, mid)] | nodes[code(mid +
1, r)];
}
bitset query(
int l,
int r)
{
g_L = l;
g_R = r;
return query_(
1, n);
}
} st;
bitset topset[maxn];
void DFS3(
int node)
{
if (node == top[node])
topset[node].
set(a[node]);
else
(topset[node] = topset[parent[node]]).
set(a[node]);
for (
int i =
0; i < G[node].size(); i++)
{
int to = G[node][i];
DFS3(to);
}
}
bitset query(
int u,
int lca)
{
bitset ret;
while (top[u] != top[lca])
{
ret |= topset[u];
u = parent[top[u]];
}
ret |= st.query(dfn[lca], dfn[u]);
return ret;
}
work()
{
DFS3(
1);
for (
int i =
1; i <= q; i++)
{
bitset set[
6];
const int* c = querys[i].c;
int lca = querys[i].lca;
for (
int j =
1; j <= c[
0]; j++)
set[j] = query(c[j], lca);
int ans = m;
int U =
1 << c[
0];
for (
int S =
1; S < U; S++)
{
int cnt =
0;
set[
0].reset();
for (
int j =
0; j < c[
0]; j++)
if (S & (
1 << j))
{
set[
0] |=
set[j +
1];
cnt++;
}
ans =
std::min(ans, (
int)
set[
0].count() / cnt);
}
printOut(ans * c[
0]);
}
}
};
void run()
{
n = readIn();
m = readIn();
q = readIn();
if (!q)
return;
G.resize(n +
1);
for (
int i =
2; i <= n; i++)
G[parent[i] = readIn()].push_back(i);
for (
int i =
1; i <= n; i++)
a[i] = readIn();
DFS1(
1);
DFS2(
1,
0);
for (
int i =
1; i <= q; i++)
querys[i].read();
if (n <=
3000 && q <=
3000)
RunInstance(brute);
else
RunInstance(work);
}
int main()
{
#ifndef LOCAL
freopen(
"party.in",
"r", stdin);
freopen(
"party.out",
"w", stdout);
#endif
run();
return 0;
}
