学步园

一开始就想着找lca，然后排序，一看80000个点，30000次操作，想着不会超时吧，就没写，，今天还是试着写了下，时间才78ms，，，

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 80001
int head[N],num,cont[N],vis[N],father[N],n,m,ans[N],k,deep[N];
struct edge
{
	int st,ed,next;
}E[N*2];
void addedge(int x,int y)
{
	E[num].st=x;
	E[num].ed=y;
	E[num].next=head[x];
	head[x]=num++;
}
int cmp(const void *a,const void *b)
{
	return *(int *)b-*(int *)a;
}
void dfs(int u)
{
	vis[u]=1;
	int i,v;
	for(i=head[u];i!=-1;i=E[i].next)
	{
		v=E[i].ed;
		if(vis[v]==1)continue;
		father[v]=u;
		deep[v]=deep[u]+1;
		dfs(v);
	}
}
void LCA(int x,int y)
{
	k=0;
	while(deep[x]>deep[y])
	{
		ans[k++]=cont[x];
		x=father[x];	   
	}
	while(deep[y]>deep[x])
	{
		ans[k++]=cont[y];
		y=father[y];
	}
	while(x!=y)
	{
		ans[k++]=cont[x];
		ans[k++]=cont[y];
		x=father[x];
		y=father[y];
	}
	ans[k++]=cont[x];
}
void find(int mm,int x,int y)
{
	LCA(x,y);
	if(k<mm)
		printf("invalid request!\n");
	else
	{
		qsort(ans,k,sizeof(ans[0]),cmp);
		printf("%d\n",ans[mm-1]);
	}
}
int main()
{
	int i,op,x,y;
	while(scanf("%d%d",&n,&m)!=-1)
	{
		memset(head,-1,sizeof(head));
		num=0;
		for(i=1;i<=n;i++)
			scanf("%d",&cont[i]);
		for(i=1;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			addedge(x,y);
			addedge(y,x);
		}
		memset(vis,0,sizeof(vis));
		deep[1]=0;father[1]=1;
		dfs(1);
		while(m--)
		{
			scanf("%d%d%d",&op,&x,&y);
			if(op==0)cont[x]=y;
			else find(op,x,y);
		}
	}
	return 0;
}