题解 CF786E 【ALT】
Walking_Dead
2020-08-06 15:23:29
[题目传送门](https://www.luogu.com.cn/problem/CF786E)
# 题目大意
给出一个 $n$ 个点的树，有 $m$ 个居民，他们都非常喜欢狗，于是，每个居民要求要么给它一条狗，要么在他散步的路径上每条边都有狗。求最少需要几个狗。
$n,m\le 2\times 10^4$
# 思路
可以看出来肯定是个网络流之类的东西，那肯定是把居民和边连起边，经过思考，你发现如果对于点 $i$ ，我们 $s\to i$ 容量为 $1$ ，$[l,r]\to t$ 容量为 $1$ ，$i \to [l,r] $ 容量为 $\infty$，答案其实就是最小割。其中 $[l,r]$ 表示该居民散步的路径上的边。至于为什么自己画一下图就知道了，就是你要么删居民要么删掉边。
然后你发现 $n^2$ 条边肯定是会爆炸的，于是我们可以线段树优化建图，边数就降到了 $n\log n$ 条，具体可以用树链剖分实现。
# $\texttt{Code}$
```cpp
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define INF 0x3f3f3f3f
#define MAXN 2000005
int n,m,top = 1,to[MAXN],wei[MAXN],cur[MAXN],nxt[MAXN],head[MAXN],fuck[MAXN];
void Add_Edge (int u,int v,int w){
to[++ top] = v,wei[top] = w,nxt[top] = head[u],head[u] = top;
to[++ top] = u,wei[top] = 0,nxt[top] = head[v],head[v] = top;
}
void build (int i,int l,int r,int fuckto){
if (l == r) return fuck[i] = l,Add_Edge (i,fuckto,1);
int mid = (l + r) >> 1,ls = i << 1,rs = i << 1 | 1;
Add_Edge (i,ls,INF),Add_Edge (i,rs,INF),build (ls,l,mid,fuckto),build (rs,mid + 1,r,fuckto);
}
void modify (int i,int l,int r,int tl,int tr,int d){
if (l >= tl && r <= tr) return Add_Edge (d,i,INF);
int mid = (l + r) >> 1,ls = i << 1,rs = i << 1 | 1;
if (tr > mid) modify (rs,mid + 1,r,tl,tr,d);
if (tl <= mid) modify (ls,l,mid,tl,tr,d);
}
int dep[MAXN];
bool BFS (int s,int t){
for (Int i = 1;i <= 4 * n + m + 2;++ i) cur[i] = head[i];
memset (dep,0x3f,sizeof (dep));
queue <int> q;while (!q.empty()) q.pop ();dep[s] = 0,q.push (s);
while (!q.empty()){
int u = q.front();q.pop ();
for (Int i = head[u];i;i = nxt[i]){
int v = to[i],w = wei[i];
if (dep[v] == INF && w){
dep[v] = dep[u] + 1;
q.push (v);
}
}
}
return dep[t] != INF;
}
int dfs (int s,int t,int lim){
if (s == t) return lim;
int used = 0;
for (Int& i = cur[s];i && lim;i = nxt[i]){
cur[s] = i;int v = to[i],w = wei[i];
if (dep[v] == dep[s] + 1 && w){
int del = dfs (v,t,min (lim,w));
used += del,lim -= del,wei[i] -= del,wei[i ^ 1] += del;
}
}
if (lim == 0) dep[s] = INF;
return used;
}
int Dinic (int s,int t){
int res = 0;
while (BFS (s,t)) res += dfs (s,t,INF);
return res;
}
#define PII pair<int,int>
#define MP make_pair
map <PII,int> cge;
struct FuckTree{
int toop = 1,to[MAXN],nxt[MAXN],tur[MAXN],id[MAXN],head[MAXN];
void Add_Edge (int u,int v){
to[++ toop] = v,nxt[toop] = head[u],head[u] = toop;
to[++ toop] = u,nxt[toop] = head[v],head[v] = toop;
}
int Index,dep[MAXN],par[MAXN],siz[MAXN],son[MAXN],top[MAXN],dfn[MAXN];
void dfs1 (int u,int fa){
par[u] = fa,dep[u] = dep[fa] + 1,siz[u] = 1,id[u] = cge[MP (u,fa)];
for (Int i = head[u];i;i = nxt[i]) if (to[i] ^ fa){
dfs1 (to[i],u),siz[u] += siz[to[i]];
if (siz[to[i]] > siz[son[u]]) son[u] = to[i];
}
}
void dfs2 (int u,int Top){
top[u] = Top,dfn[u] = ++ Index,tur[Index] = u;
if (son[u]) dfs2 (son[u],Top);
for (Int i = head[u];i;i = nxt[i])
if (to[i] != par[u] && to[i] != son[u]) dfs2 (to[i],to[i]);
}
void Init (){dfs1 (1,0),dfs2 (1,1);}
void Modify (int u,int v,int x){
while (top[u] ^ top[v]){
if (dep[top[u]] < dep[top[v]]) swap (u,v);
modify (1,1,n,dfn[top[u]],dfn[u],x),u = par[top[u]];
}
if (dfn[u] > dfn[v]) swap (u,v);
if (u ^ v) modify (1,1,n,dfn[u] + 1,dfn[v],x);
}
}Tree;
bool vis[MAXN];
void dfs2 (int u){
vis[u] = 1;
for (Int i = head[u];i;i = nxt[i])
if (wei[i] && !vis[to[i]]) dfs2 (to[i]);
}
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
signed main(){
read (n,m);
for (Int i = 2,u,v;i <= n;++ i) read (u,v),Tree.Add_Edge (u,v),cge[MP (u,v)] = cge[MP (v,u)] = i - 1;Tree.Init ();
int s = n * 4 + m + 1,t = n * 4 + m + 2;build (1,1,n,t);
for (Int i = 1,l,r;i <= m;++ i) read (l,r),Tree.Modify (l,r,n * 4 + i),Add_Edge (s,n * 4 + i,1);
write (Dinic (s,t)),putchar ('\n');dfs2 (s);
vector <int> people,edge;
for (Int i = head[s];i;i = nxt[i]) if (!vis[to[i]]) people.push_back (to[i] - 4 * n);
for (Int i = head[t];i;i = nxt[i]) if (vis[to[i]]) edge.push_back (Tree.id[Tree.tur[fuck[to[i]]]]);
write (people.size()),putchar (' ');for (Int i = 0;i < people.size();++ i) write (people[i]),putchar (' ');putchar ('\n');
write (edge.size()),putchar (' ');for (Int i = 0;i < edge.size();++ i) write (edge[i]),putchar (' ');putchar ('\n');
return 0;
}
```
# 附
## checker 判断你的答案是否合法
```cpp
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define MAXN 20005
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
int n,m,vis[MAXN],dep[MAXN],toop = 1,fa[MAXN],to[MAXN],nxt[MAXN],sum[MAXN],head[MAXN],a1[MAXN],a2[MAXN],al[MAXN],ar[MAXN];
void Add_Edge (int u,int v){to[++ toop] = v,nxt[toop] = head[u],head[u] = toop;}
void dfs (int u,int par){
fa[u] = par,dep[u] = dep[par] + 1;
for (Int i = head[u];i;i = nxt[i]){
int v = to[i];if (v == par) continue;
dfs (v,u);
}
}
void dfs2 (int u){
for (Int i = head[u];i;i = nxt[i])
if (to[i] != fa[u]) dfs2 (to[i]);
}
bool check (int l,int r){
bool flag = 1;
while (l ^ r){
if (dep[l] < dep[r]) swap (l,r);
if (!sum[l]) return 0;l = fa[l];
}
return 1;
}
signed main(){
read (n,m);
for (Int i = 2,u,v;i <= n;++ i) read (u,v),a1[i - 1] = u,a2[i - 1] = v,Add_Edge (u,v),Add_Edge (v,u);
for (Int i = 1;i <= m;++ i) read (al[i],ar[i]);dfs (1,0);
int tot,tot1,tot2;read (tot,tot1);
for (Int i = 1,a;i <= tot1;++ i) read (a),vis[a] = 1;
read (tot2);for (Int i = 1,a;i <= tot2;++ i) read (a),sum[fa[a1[a]] == a2[a] ? a1[a] : a2[a]] = 1;
for (Int i = 1;i <= m;++ i) if (!check (al[i],ar[i]) && !vis[i]) return puts ("You Fucking WA!"),0;
puts ("Right!!!");
return 0;
}
```
## datamaker 生成数据
```cpp
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define MAXN
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
signed main(){
freopen ("data.in","w",stdout);
srand (time (NULL));
int n = rand() % 100 + 1,m = rand() % n + 1;cout << n << " " << m << endl;
for (Int i = 2;i <= n;++ i) cout << i << " " << rand() % (i - 1) + 1 << endl;
for (Int i = 1;i <= m;++ i) cout << rand () % n + 1 << " " << rand() % n + 1 << endl;
return 0;
}
```