【bzoj4203】【JZ雅礼联考】同桌的你 题解

题目大意

  共有n个同学，每个同学性别为 b[i] ，最喜欢的人是 a[i]。注意喜欢是单向的。
  小A希望能够出现尽可能多的同桌，满足同桌两人中存在一人，喜欢另一个人。不妨称这样的同桌叫“满意同桌”。
  在满足出现尽可能多的“满意同桌”的前提下，最大化男女同桌的组数。
  并输出其中一种方案。
  n<=10^6

【20%】n<=20

  枚举每个人是否和TA喜欢的人成为同桌。

【100%】n<=10^6

  这是经典的环套树模型。
  先考虑一棵树怎么做。设 f[i,0/1] 表示第 i 个人，选还是不选，得到的最大答案（答案有两个值，是二维的）。规定每个点要是选的话，只能选TA的儿子。这就是个经典树形dp。
  而这题的环套树有个很好的性质：假设我断开了环上的 x->y 这条边，然后dp。若这时候的答案不是最优的，意味着 x 要跟 y 组一对，等价于连向 x 的那条边和 y 连出去的那条边都没有意义。那么把这两条其中一条边断掉，连上 x->y ，再做一遍dp，得出来就是最优答案。

  至于输出一种方案，就记录每个状态从哪里来就行了。
  时间总共是两遍dp，加上一些琐碎的东西，总共O(n)。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef pair<int,int> PAR;
bool operator > (PAR a,PAR b) {return a.first>b.first || a.first==b.first && a.second>b.second;}
PAR operator + (PAR a,PAR b) {return make_pair(a.first+b.first, a.second+b.second);}
PAR operator - (PAR a,PAR b) {return make_pair(a.first-b.first, a.second-b.second);}

const int maxn=1e6+5;

int n,fa[maxn],sex[maxn];

int tot,go[maxn],next[maxn],f1[maxn],fav[maxn];
void ins(int x,int y)
{
	go[++tot]=y;
	next[tot]=f1[x];
	f1[x]=tot;
	fav[y]=tot;
}

int com[maxn],roll[maxn],d[maxn];
void find_roll()
{
	int j=0;
	fo(i,1,n) if (!com[i]) d[++j]=i;
	
	for(int i=1; i<=j; i++)
	{
		if (--com[fa[d[i]]]==0) d[++j]=fa[d[i]];
	}
	
	roll[0]=0;
	fo(i,1,n) if (com[i]) roll[++roll[0]]=i;
}
void make_d(int k,int pn)
{
	d[ d[0]=1 ]=k;
	for(int i=1; i<=d[0]; i++)
	{
		for(int p=f1[d[i]]; p; p=next[p]) if (p!=pn) d[++d[0]]=go[p];
	}
}

PAR f[2][maxn][2],g[2][maxn];
int fro[2][maxn];
bool bz[maxn];
void bfs_dp(int ty,int k,int pn)
{
	fd(i,d[0],1)
	{
		int k=d[i];
		
		bz[d[i]]=1;
		PAR sum=make_pair(0,0);
		for(int p=f1[k]; p; p=next[p]) if (p!=pn) sum=sum+g[ty][go[p]];
		
		f[ty][k][0]=sum;
		f[ty][k][1]=make_pair(0,0);
		fro[ty][k]=0;
		for(int p=f1[k]; p; p=next[p]) if (p!=pn)
		{
			PAR t=sum-g[ty][go[p]]+f[ty][go[p]][0];
			t.first++;
			t.second+=sex[go[p]]^sex[k];
			if (t>f[ty][k][1])
			{
				f[ty][k][1]=t;
				fro[ty][k]=go[p];
			}
		}
		if (f[ty][k][0]>f[ty][k][1])
		{
			g[ty][k]=f[ty][k][0];
			fro[ty][k]=0;
		} else g[ty][k]=f[ty][k][1];
	}
}
int cp[maxn][2],cp0;
void bfs_ans(int ty,int k,int pn)
{
	fo(i,1,d[0])
	{
		int k=d[i];
		
		if (fro[ty][k]) cp[++cp0][0]=k, cp[cp0][1]=fro[ty][k];
		for(int p=f1[k]; p; p=next[p]) if (p!=pn)
		{
			if (go[p]==fro[ty][k]) fro[ty][go[p]]=0;
		}
	}
}

int T;
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		tot=0;
		memset(f1,0,sizeof(f1));
		
		memset(com,0,sizeof(com));
		scanf("%d",&n);
		fo(i,1,n)
		{
			scanf("%d %d",&fa[i],&sex[i]);
			sex[i]--;
			com[fa[i]]++;
			ins(fa[i],i);
		}
		
		find_roll();
		
		memset(bz,0,sizeof(bz));
		int ans1=0, ans2=0;
		cp0=0;
		fo(x,1,n) if (!bz[x] && com[x])
		{
			make_d(x,fav[x]);
			bfs_dp(0,x,fav[x]);
			make_d(fa[x],fav[fa[x]]);
			bfs_dp(1,fa[x],fav[fa[x]]);
			
			if (g[0][x]>g[1][fa[x]])
			{
				ans1+=g[0][x].first, ans2+=g[0][x].second;
				make_d(x,fav[x]);
				bfs_ans(0,x,fav[x]);
			} else
			{
				ans1+=g[1][fa[x]].first, ans2+=g[1][fa[x]].second;
				bfs_ans(1,fa[x],fav[fa[x]]);
			}
		}
		
		printf("%d %d\n",ans1,ans2);
		fo(i,1,ans1) printf("%d %d\n",cp[i][0],cp[i][1]);
	}
}