题目链接：CF786E
输出方案暗示网络流
我们考虑最朴素的建图
由源点\(s\)连向所有人，容量为1；树上所有的边视作节点连向\(t\)，流量为1；人向其路径上所有的树边连边，流量为\(inf\)，跑最小割即可
然而我们发现这样的话网络图中的边的数据规模达到了\(O(n^2)\)，肯定炸掉
于是考虑优化建图
我们将一条路径拆成\(log\)段，用\((i,j)\)表示由节点\(i\)跳到其\(2^j\)层父亲
注意到\((i,j)\)包含着\((i,j-1),(i+2^{j-1},j-1)\)，因此我们考虑也将其连上容量为\(inf\)的边（类似于标记下放？不熟悉的可以做SCOI2016萌萌哒，一个区间上的问题）
原来的图中将树边连向\(t\)也就变成了将边\((i,0)\)连向\(t\)（此时\(t>1\)）
那么新图的点数和边数的规模均维持在\(O(nlogn)\)可以维护
然而毒瘤题还要输出方案
我们考虑从源点\(dfs\)，如果当前找到的一条边有流量说明还未割开
如果代表人的点被割开说明要标记这个人；如果某条原来与\(t\)相连的树边未被割开说明要标记这一条树边
预处理时存下相对应的编号即可
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define lowbit(x) (x)&(-x)
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,a,b) for (int i=a;i>=b;i--)
#define maxd 1000000007
typedef long long ll;
const int N=100000;
const double pi=acos(-1.0);
struct treenode{
int to,nxt,id;
}tree[40040];
int all1=0,head1[40040];
struct flownode{
int to,nxt,flow;
}sq[10004000];
int all=1,head[501000],cur[500500],dept[500500];
bool vis[500500];
queue<int> q;
int n,m,st[20020][20],fa[20020][20],tot=0,dep[20020],s,t,
a[500500],b[500500];
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;
}
void addedge(int u,int v,int id)
{
all1++;tree[all1].nxt=head1[u];tree[all1].to=v;tree[all1].id=id;head1[u]=all1;
}
void add(int u,int v,int f)
{
all++;sq[all].nxt=head[u];sq[all].to=v;sq[all].flow=f;head[u]=all;
all++;sq[all].nxt=head[v];sq[all].to=u;sq[all].flow=0;head[v]=all;
}
void dfs(int u,int fu)
{
dep[u]=dep[fu]+1;fa[u][0]=fu;
rep(i,1,15) st[u][i]=(++tot);
rep(i,1,15)
{
if (fa[u][i-1])
{
fa[u][i]=fa[fa[u][i-1]][i-1];
add(st[u][i],st[u][i-1],maxd);
add(st[u][i],st[fa[u][i-1]][i-1],maxd);
}
}
int i;
for (i=head1[u];i;i=tree[i].nxt)
{
int v=tree[i].to;
if (v==fu) continue;
st[v][0]=(++tot);b[tree[i].id]=tot;
dfs(v,u);
}
}
void query_lca(int u,int v,int now)
{
if (dep[u]<dep[v]) swap(u,v);
int tmp=dep[u]-dep[v];
per(i,15,0)
{
if ((tmp>>i)&1)
{
add(now,st[u][i],maxd);
u=fa[u][i];
}
}
if (u==v) return;
per(i,15,0)
{
if (fa[u][i]!=fa[v][i])
{
add(now,st[u][i],maxd);add(now,st[v][i],maxd);
u=fa[u][i];v=fa[v][i];
}
}
add(now,st[u][0],maxd);add(now,st[v][0],maxd);
}
void init()
{
n=read();m=read();
rep(i,1,n-1)
{
int u=read(),v=read();
addedge(u,v,i);addedge(v,u,i);
}
rep(i,0,15) st[0][i]=(++tot);st[1][0]=(++tot);
dfs(1,0);
rep(i,1,m)
{
a[i]=(++tot);add(s,tot,1);
int u=read(),v=read();
query_lca(u,v,tot);
}
t=(++tot);
rep(i,2,n) add(st[i][0],t,1);
}
bool bfs()
{
memset(vis,0,sizeof(vis));
memset(dept,0,sizeof(dept));
q.push(s);vis[s]=1;
while (!q.empty())
{
int u=q.front(),i;q.pop();
for (i=head[u];i;i=sq[i].nxt)
{
int v=sq[i].to;
if ((sq[i].flow) && (!vis[v]))
{
vis[v]=1;q.push(v);
dept[v]=dept[u]+1;
}
}
}
if (!vis[t]) return 0;
rep(i,0,t) cur[i]=head[i];
return 1;
}
int dfs(int now,int t,int lim)
{
if ((!lim) || (now==t)) return lim;
int i,sum=0;
for (i=cur[now];i;i=sq[i].nxt)
{
int v=sq[i].to;cur[now]=i;
if (dept[v]==dept[now]+1)
{
int f=dfs(v,t,min(sq[i].flow,lim));
if (f)
{
sq[i].flow-=f;
sq[i^1].flow+=f;
sum+=f;lim-=f;
if (!lim) break;
}
}
}
return sum;
}
void dfsans(int u)
{
vis[u]=1;
int i;
for (i=head[u];i;i=sq[i].nxt)
{
int v=sq[i].to;
if ((!vis[v]) && (sq[i].flow)) dfsans(v);
}
}
void work()
{
int ans=0;
while (bfs()) ans+=dfs(s,t,maxd);
memset(vis,0,sizeof(vis));
dfsans(0);
printf("%d\n",ans);
int cnt=0;
rep(i,1,m) if (!vis[a[i]]) cnt++;
printf("%d ",cnt);
rep(i,1,m) if (!vis[a[i]]) printf("%d ",i);printf("\n");
cnt=0;
rep(i,1,n-1) if (vis[b[i]]) cnt++;
printf("%d ",cnt);
rep(i,1,n-1) if (vis[b[i]]) printf("%d ",i);
}
int main()
{
init();
work();
return 0;
}