为什么你们第一眼都能想到最小割，我第一眼都只能想到费用流。
为什么你们的做法都这么短，我一写就是 \(5KB\)。
费用流有一个基本矛盾，就是守卫只需拥有一只狗和每一个人都需要守卫有狗的基本矛盾。由于需求与供给不平衡，所以流量不好确定。如果有人费用流过了来长沙火车站，疯狂星期四我V你50。
由于最小，我们想到最小割。我们想要两种割边，一种割树上的边，一种割人。
因此我们这么构造：对于树上每条边，我们建立一个入点一个出点，源点朝入点连边，流量为 \(1\)，出点向汇点连边，流量为 \(inf\)（只需要割入点就行）。
对于每个人走过的路径 \([l,r]\) （经过树链剖分处理后变为一个区间），我们将区间里的点各自分成两个点之后再分别连到一个新点上，再把两个新点连起来，流量为 \(1\)，代表一个人。
你发现了区间连边的操作，于是可以线段树优化建图。
提供样例一的完整建图，其中 \(1\) 为源点，\(2\) 为汇点：
略微卡常。
#include <bits/stdc++.h>
#define F(i, n) for (int i = 1; i <= n; ++i)
#define ll long long
using namespace std;
const ll N = 1e6 + 5, INF = 5e7;
template<typename T> bool chkmax(T &a, T b) { return a < b ? (a = b, 1) : 0; }
template<typename T> bool chkmin(T &a, T b) { return a > b ? (a = b, 1) : 0; }
template<typename T> T read() { T a;cin >> a;return a; }
inline int read() {
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n, m, s, t;
template<const int M>
struct graph {
int st[M], nx[M * 6], to[M * 6], cur[M], cnt = 1;
int id[M * 6];
int val[M * 6];
void add(int u, int v, int w, int i) {
to[++cnt] = v;val[cnt] = w;nx[cnt] = st[u];st[u] = cnt;
id[cnt] = i;
}
};
#define go(g, u, v, w) for (int i = g.cur[u], v = g.to[i], w = g.val[i]; i; i = g.nx[i], v = g.to[i], w = g.val[i])
int cnt;
graph<N> g;
namespace Graph {
void add(int u, int v, int w, int id) {
g.add(u, v, w, id);
g.add(v, u, 0, 0);
}
int lev[N];
bool bfs(int s, int t) {
for (int i = 1; i <= cnt; ++i) lev[i] = -1;
lev[s] = 0;
for (int i = 1; i <= cnt; ++i) g.cur[i] = g.st[i];
queue<int> q;q.push(s);
while (!q.empty()) {
int u = q.front();q.pop();
go(g, u, v, w) {
if (w > 0 && lev[v] == -1)
lev[v] = lev[u] + 1, q.push(v);
}
}
return lev[t] != -1;
}
int dfs(int u, int flow, int t) {
if (u == t) return flow;
int res = flow;
for (int i = g.cur[u]; i && res; i = g.nx[i]){
int v = g.to[i], w = g.val[i];
g.cur[u] = i;
if (w > 0 && lev[v] == lev[u] + 1) {
int c = dfs(v, min(w, res), t);res -= c;
g.val[i] -= c;g.val[i ^ 1] += c;
}
}
return flow - res;
}
int dinic(int s, int t) {
int ans = 0;
while (bfs(s, t)) {
int p = dfs(s, INF, t);
ans += p;
}
return ans;
}
}
using Graph::add;
using Graph::dinic;
vector<tuple<int, int>> tree[N];
long long dfn[N];
int siz[N], son[N], top[N], dep[N], fa[N], pos[N], I[N];
namespace pou {
int tot = 0;
void findSon(int u, int F) {
siz[u] = 1;fa[u] = F;
int v, id;
for (auto p : tree[u]) {
tie(v, id) = p;
if (v == F) continue;
I[v] = id;
dep[v] = dep[u] + 1;
findSon(v, u);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
return ;
}
void mark(int u, int fa, int to) {
int v, id;
if (u != 1) {
dfn[u] = ++tot;
pos[tot] = u;
}
top[u] = to;
if (son[u]) mark(son[u], u, to);
for (auto p : tree[u]) {
tie(v, id) = p;
if (v == fa || v == son[u]) continue;
mark(v, u, v);
}
}
}
int upId[N], dwId[N], upSon[N][2], dwSon[N][2], upRt, dwRt;
tuple<int, int> build(int l, int r) {
if (l == r) {
upId[l] = ++cnt;
dwId[l] = ++cnt;
return tie(upId[l], dwId[l]);
}
int mid = (l + r) >> 1;
int u1 = ++cnt;
int u2 = ++cnt;
tie(upSon[u1][0], dwSon[u2][0]) = build(l, mid);
tie(upSon[u1][1], dwSon[u2][1]) = build(mid + 1, r);
add(upSon[u1][0], u1, INF, 0);
add(upSon[u1][1], u1, INF, 0);
add(u2, dwSon[u2][0], INF, 0);
add(u2, dwSon[u2][1], INF, 0);
return tie(u1, u2);
}
int v1, v2;
void lian(tuple<int, int> u, int l, int r, int fl, int fr) {
int u1, u2; tie(u1, u2) = u;
if (fl <= l && r <= fr) {
add(u1, v1, INF, 0);
add(v2, u2, INF, 0);
return ;
}
int mid = (l + r) >> 1;
if (mid >= fl) lian(tie(upSon[u1][0], dwSon[u2][0]), l, mid, fl, fr);
if (mid < fr) lian(tie(upSon[u1][1], dwSon[u2][1]), mid + 1, r, fl, fr);
}
void jump(int u1, int u2){
while (top[u1] != top[u2]) {
if (dep[top[u1]] < dep[top[u2]]) swap(u1, u2);
if (top[u1] == 1) {
lian(tie(upRt, dwRt), 1, n - 1, dfn[son[top[u1]]], dfn[u1]);
}
else {
lian(tie(upRt, dwRt), 1, n - 1, dfn[top[u1]], dfn[u1]);
}
u1 = fa[top[u1]];
}
if (u1 == u2) return ;
if (dep[u1] > dep[u2]) swap(u1, u2);
if (dfn[son[u1]] <= dfn[u2]) lian(tie(upRt, dwRt), 1, n - 1, dfn[son[u1]], dfn[u2]);
}
bool vis[N];
void dfs(int u) {
vis[u] = 1;
go(g, u, v, w) {
if (w == 0 || vis[v]) continue;
dfs(v);
}
}
int main(){
freopen("text.in", "r", stdin);
int u, v;
dfn[0] = INF;
s = ++cnt;t = ++cnt;
n = read(), m = read();
int pd = 1;
F(i, n - 1) {
u = read(), v = read();
tree[u].push_back(tie(v, i));
tree[v].push_back(tie(u, i));
}
pou::findSon(1, 0);
pou::mark(1, 0, 1);
tie(upRt, dwRt) = build(1, n - 1);
F(i, n - 1) {
add(s, upId[i], 1, I[pos[i]]);
add(dwId[i], t, INF, 0);
}
F(i, m) {
u = read(), v = read();
v1 = ++cnt; v2 = ++cnt;
add(v1, v2, 1, i + n);
jump(u, v);
}
printf("%d\n", dinic(s, t));
dfs(s);
vector<int> edge, peo;
for (int i = g.st[s]; i; i = g.nx[i]) {
if (vis[g.to[i]] == false && g.val[i] == 0) edge.push_back(g.id[i]);
}
for (int i = 2; i <= cnt; ++i) {
for (int j = g.st[i]; j; j = g.nx[j]) {
if (vis[i] != vis[g.to[j]] && g.id[j] > n && g.val[j] == 0) {
peo.push_back(g.id[j] - n);
}
}
}
printf("%ld ", peo.size());
for (auto i : peo) printf("%d ", i);
puts("");
printf("%ld ", edge.size());
for (auto i : edge) printf("%d ", i);
return 0;
}