记录编号	188338	评测结果	AAAAAAAAAA
题目名称	[POI 2003]可爱的猴子	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.558 s
提交时间	2015-09-22 19:30:13	内存使用	9.28 MiB

#include<cstdio>
#include<iostream>
using namespace std;
const int SIZEN=200010,SIZEM=400010;
int N,M;
int L[SIZEN][3];
bool ch[SIZEN][3]={0};//标记边在最后是否还存在
int last[SIZEN]={0};
int m[SIZEM],h[SIZEM],f[SIZEN]={0};
class miku
{
public:
	int x,next;
	miku()
	{
		x=-1;next=0;
	}
}P[SIZEN];//链表
void change(int x,int t)
{
	P[x].x=t;
}
int find(int x)
{
	if(x==f[x])
		return x;
	else return f[x]=find(f[x]);
}
void linkP(int x,int y)
{
	int tem=x;
	while(P[tem].next!=0) tem=P[tem].next;
	P[tem].next=y;
}
void link(int x,int y,int t)
{
	int temx=find(x),temy=find(y);
	if(temx==temy) return;
	if(temx==1) {f[temy]=temx;linkP(last[temx],temy);change(temy,t);last[temx]=last[temy];}
	else {f[temx]=temy;linkP(last[temy],temx);if(temy==1)change(temx,t);last[temy]=last[temx];}
}
void read()
{
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++)
		scanf("%d%d",&L[i][1],&L[i][2]);
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d",&m[i-1],&h[i-1]);
		ch[m[i-1]][h[i-1]]=1;
	}
}
void work()
{
	for(int i=1;i<=N;i++) {f[i]=i;last[i]=i;}
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=2;j++)
		{
			if(ch[i][j]==0&&L[i][j]!=-1)
				link(i,L[i][j],-1);
		}
	}
	//for(int i=1;i<=N;i++)
	//	cout<<i<<" "<<f[i]<<endl;
	for(int i=M-1;i>=0;i--)
	{
		link(m[i],L[m[i]][h[i]],i);
		//for(int j=1;j<=N;j++)
		//	cout<<j<<" "<<P[j].x<<" "<<P[j].next<<" "<<f[j]<<endl;
	}
	int tem=1,now=-1;
	while(tem!=0)
	{
		if(P[tem].x==-1) P[tem].x=now;
		else now=P[tem].x;
		tem=P[tem].next;
	}
	for(int i=1;i<=N;i++)
		printf("%d\n",P[i].x);
}
int main()
{
	freopen("monkeya.in","r",stdin);
	freopen("monkeya.out","w",stdout);
	read();
	work();
	return 0;
}