bzoj1146 [CTSC2008]网络管理Network

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define N 80010
#define TT 3000010
#define inf 1000000000
using namespace std;
inline 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;
}
//===============================================
int n,m;
int v[N];
int bin[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};
//===============================================
struct edge{int to,next;}e[2*N];
int head[N],cnt;
inline void ins(int u,int v)
{
	e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
	e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;
}
//===============================================
int l[TT],r[TT],rnd[TT],dat[TT],son[TT],rep[TT],root[4*N];
int treesize,wrk;
inline void update(int k){son[k]=son[l[k]]+son[r[k]]+rep[k];}
inline void tree_print(int k)
{
	if(!k)return;
	tree_print(l[k]);
	printf("%d*%d ",dat[k],rep[k]);
	tree_print(r[k]);
}
inline void right_rotate(int &k)
{
	int t=l[k];
	l[k]=r[t];
	r[t]=k;
	son[t]=son[k];
	update(k);
	k=t;
}
inline void left_rotate(int &k)
{
	int t=r[k];
	r[k]=l[t];
	l[t]=k;
	son[t]=son[k];
	update(k);
	k=t;
}
inline void insert(int &k,int x)
{
	if (!k){k=++treesize;rnd[k]=rand();dat[k]=x;rep[k]=son[k]=1;return;}
	son[k]++;
	if (x==dat[k]){rep[k]++;return;}
	else if (x<dat[k])
	{
		insert(l[k],x);
		if (rnd[l[k]]>rnd[k])right_rotate(k);
	}else if (x>dat[k])
	{
		insert(r[k],x);
		if (rnd[r[k]]>rnd[k])left_rotate(k);
	}
}
inline void del(int &k,int x)
{
	if (!k)return;
	if (x==dat[k])
	{
		if (rep[k]>1){rep[k]--;son[k]--;return;}
		if (l[k]*r[k]==0)k=l[k]+r[k];
		else if (rnd[l[k]]>rnd[r[k]]){right_rotate(k);del(k,x);}
		else {left_rotate(k);del(k,x);}
	}else if (x<dat[k])del(l[k],x),son[k]--;
	else del(r[k],x),son[k]--;
}
inline void buildtree(int k,int l,int r,int x,int d)
{
	insert(root[k],d);
	if (l==r)return;
	int mid=(l+r)>>1;
	if (x<=mid)buildtree(k<<1,l,mid,x,d);
	else buildtree(k<<1|1,mid+1,r,x,d);
}
inline void get_rank(int k,int x)
{
	if (!k)return;
	if (x==dat[k]){wrk+=son[r[k]];return;}
	if (x<dat[k])
	{
		wrk+=son[r[k]]+rep[k];
		get_rank(l[k],x);
	}else if (x>dat[k])get_rank(r[k],x);
}
inline void ask_rank(int k,int l,int r,int x,int y,int d)
{
	if (l==x&&r==y){get_rank(root[k],d);return;}
	int mid=(l+r)>>1;
	if (y<=mid)ask_rank(k<<1,l,mid,x,y,d);
	else if (x>mid)ask_rank(k<<1|1,mid+1,r,x,y,d);
	else
	{
		ask_rank(k<<1,l,mid,x,mid,d);
		ask_rank(k<<1|1,mid+1,r,mid+1,y,d);
	}
}
inline void change(int k,int l,int r,int pos,int x,int y)
{
	del(root[k],x);insert(root[k],y);
	if(l==r)return;
	int mid=(l+r)>>1;
	if(pos<=mid)change(k<<1,l,mid,pos,x,y);
	else change(k<<1|1,mid+1,r,pos,x,y);
}
//===============================================
int place[4*N],pplace[4*N],belong[4*N];
int tt;
int size[N],fa[N][16],dep[N];
bool mrk[N];
inline void dfs1(int x,int d)
{
	if (mrk[x])return;mrk[x]=1;
	size[x]=1;dep[x]=d;
	for (int i=1;i<16;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for (int i=head[x];i;i=e[i].next)
		if (!mrk[e[i].to])
		{
			fa[e[i].to][0]=x;
			dfs1(e[i].to,d+1);
			size[x]+=size[e[i].to];
		}
}
inline void dfs2(int x,int chain)
{
	place[x]=++tt;pplace[tt]=x;belong[x]=chain;
	int mx=-1,res=-1;
	for (int i=head[x];i;i=e[i].next)
	if (e[i].to!=fa[x][0])
	{
		if (size[e[i].to]>mx)
		{
			mx=size[e[i].to];
			res=e[i].to;
		}
	}
	if (res==-1)return;
	dfs2(res,chain);
	for (int i=head[x];i;i=e[i].next)
		if (e[i].to!=res&&e[i].to!=fa[x][0])
			dfs2(e[i].to,e[i].to);
}
inline int LCA(int a,int b)
{
	if (dep[a]<dep[b])swap(a,b);
	int des=dep[a]-dep[b];
	for (int i=0;i<16;i++)
		if (des & (1<<i))a=fa[a][i];
	for (int i=15;i>=0;i--)
		if (fa[a][i]!=fa[b][i])
		{
			a=fa[a][i];
			b=fa[b][i];
		}
	if (a==b)return a;
	else return fa[a][0];
}
inline void calc(int from,int to,int d)
{
	int l,r;
	while (belong[from]!=belong[to])
	{
		l=place[belong[from]];
		r=place[from];
		ask_rank(1,1,n,l,r,d);
		from=fa[belong[from]][0];
	}
	if (place[to]+1<=place[from])
		ask_rank(1,1,n,place[to]+1,place[from],d);
}
int main()
{
	srand(1);
	n=read();m=read();
	for (int i=1;i<=n;i++)v[i]=read();
	for (int i=1;i<n;i++)
	{
		int x=read(),y=read();
		ins(x,y);
	}
	dfs1(1,0);
	dfs2(1,1);
	for (int i=1;i<=n;i++)buildtree(1,1,n,place[i],v[i]);
	for (int i=1;i<=m;i++)
	{
		int k=read(),a=read(),b=read();
		if (!k)
		{
			change(1,1,n,place[a],v[a],b);
			v[a]=b;
		}else 
		{
			int lca=LCA(a,b);
			if (dep[a]+dep[b]+1-2*dep[lca]<k)
			{
				printf("invalid request!\n");
				continue;
			}
			int L=0,R=inf,ans=0;
			while (L<=R)
			{
				int md=(L+R)>>1;
				wrk=0;
				if(a!=lca)calc(a,lca,md);
				if(b!=lca)calc(b,lca,md);
				if (v[lca]>md)wrk++;
				if (wrk<k){ans=md;R=md-1;}
				else L=md+1;
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}