记录编号	251859	评测结果	AAATTTTTTT
题目名称	[HNOI 2016] 网络	最终得分	30
用户昵称	Satoshi	是否通过	未通过
代码语言	C++	运行时间	1.980 s
提交时间	2016-04-18 18:51:47	内存使用	25.87 MiB

#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#define N 200010
#define M 20
using namespace std;
ifstream in("network_tenderRun.in");
ofstream out("network_tenderRun.out");
bool vis[N]={0};
int deep[N]={0};
int p[N][M+5]={0};
vector<int> G[N];
int n,q;
bool broken[N]={0};
int tim[N]={0};
class edge
{
public:
	int u,v,w;
	void make(int a,int b,int c){u=a;v=b;w=c;}
	void print(){out<<u<<' '<<v<<' '<<w<<endl;}
}E[N];
int top=0;
inline int LCA(int u,int v)
{
	int i,d;
	if(deep[u]<deep[v])swap(u,v);
	d=deep[u]-deep[v];
	for(i=0;i<M;i++)if((1<<i)&d)u=p[u][i];
	if(u==v)return u;
	for(i=M-1;i>=0;i--)
	{
		if(p[u][i]!=p[v][i])
		{
			u=p[u][i];
			v=p[v][i];
		}
	}
	u=p[u][0];
	return u;
}
inline int dis(int u,int v)
{
	int fa,ans=0;
	fa=LCA(u,v);
	ans=deep[u]+deep[v]-2*deep[fa];
	return ans;
}
inline bool online(int u,int v,int x)
{
	if(dis(u,x)+dis(v,x)==dis(u,v))return 1;
	return 0;
}
void LCB(int u)
{
	int i;
	vis[u]=1;
	for(i=1;i<M;i++)
	{
		p[u][i]=p[p[u][i-1]][i-1];
		if(!p[u][i])break;
	}
	for(i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(!vis[v])LCB(v);
	}
}
void BFS(int s)
{
	int i,u,v;
	queue<int> q;
	memset(vis,0,sizeof(vis));
	memset(deep,0,sizeof(deep));
	vis[s]=1;
	q.push(s);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		for(i=0;i<G[u].size();i++)
		{
			v=G[u][i];
			if(!vis[v])
			{
				vis[v]=1;
				deep[v]=deep[u]+1;
				p[v][0]=u;
				q.push(v);
			}
		}
	}
}
void read()
{
	int i,u,v;
	in>>n>>q;
	for(i=1;i<n;i++)
	{
		in>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
}
void init()
{
	BFS(1);
	memset(vis,0,sizeof(vis));
	LCB(1);
}
void test()
{
	/*int i;
	for(i=1;i<=n;i++)out<<i<<' ';
	out<<endl;
	for(i=1;i<=n;i++)out<<deep[i]<<' ';
	out<<endl;*/
	//out<<online(2,13,6)<<endl;
}
int query(int x)
{
	int i,ans=-1;
	for(i=1;i<=top;i++)
	{
		if(!broken[i])
		{
			if(!online(E[i].u,E[i].v,x))
			{
				ans=max(ans,E[i].w);
			}
		}
	}
	return ans;
}
void work()
{
	int i,type,ti=0;
	for(i=1;i<=q;i++)
	{
		in>>type;
		ti++;
		if(type==0)
		{
			int a,b,v;
			in>>a>>b>>v;
			E[++top].make(a,b,v);
			tim[ti]=top;
			//E[top].print();
		}
		if(type==1)
		{
			int t;
			in>>t;
			//out<<t<<' '<<tim[t]<<endl;
			//out<<tim[t]<<endl;
			broken[tim[t]]=1;
		}
		if(type==2)
		{
			int x;
			in>>x;
			out<<query(x)<<endl;
		}
	}
	/*for(i=1;i<=top;i++)out<<broken[i]<<' ';
	out<<endl;*/
}
int main()
{
	read();
	init();
	work();
	//out<<online()
	//test();
	return 0;
}