码风

概览

1.所有的 include 必须 放在整个程序开头，应该使用 #include<bits/stdc++.h，除非为了卡常

2.应该 使用 using namespace std，除非为了卡常

3.main 函数 必须 放在整个程序的末尾，且 应该 使用 signed main(void)

4.禁止 使用 int 代替 bool 表示逻辑值

缺省源一般如下：

#include <bits/stdc++.h>
#define inl inline
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define pre(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
using namespace std;
signed main(void){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
}

预编译指令

若使用 C 标准库头文件，必须 使用 c 前缀

所有预编译指令除定义在 namespace 以内的 禁止 缩进

缩进

使用 4 空格的 Tab 而不是空格缩进

花括号

不换行。且左花括号的左边 禁止 有空格

所有右花括号必须与上一级代码块的缩进相同。

行

每行可以有多个语句，例如

int n;cin>>n;

dfs1(1,0);dfs2(1,1);

但是每行的语句必须意义紧密相关，否则除压行外 不应 放在一行

不应 有单独的一个空行。

变量

应该 尽量少用全局变量

局部变量 应该 在用时定义，变量名 不应该 与全局变量重名

数组可以定义 N 来表示数组长度

空格

禁止 使用空格

命名

const int 应该 全部大写，特殊的，inf 小写

结构体的第一个字母大写，其余小写

其他一律小写

封装

使用 namespace 而不是 struct

对于一个有多个函数的模板，必须 封装

对于一些意义密切相关的函数，应该 封装

其他不封装

示例：

P4116 Qtree3，树剖

#include <bits/stdc++.h>
#define inl inline
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define pre(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
using namespace std;
const int N=100010,inf=0x3f3f3f3f;
vector<int>e[N];
int n,q,w[N],fa[N],dep[N],sz[N],sn[N],top[N],rnk[N],dfn[N],sum[N<<2],cnt;
namespace Tree{
	#define ls k<<1
	#define rs k<<1|1
	#define mid (l+r>>1)
	#define pushup(k) sum[k]=min(sum[ls],sum[rs])
	inl void update(int k,int l,int r,int x){
		if(x<l||x>r)return;
		if(l==r){
			sum[k]=(sum[k]==inf?x:inf);
			return ;
		}
		update(ls,l,mid,x);
		update(rs,mid+1,r,x);
		pushup(k);
	}
	inl int query(int k,int l,int r,int x,int y){
		if(y<l||x>r)return inf;
		if(x<=l&&y>=r)return sum[k];
		return min(query(ls,l,mid,x,y),query(rs,mid+1,r,x,y));
	}
}
using namespace Tree;
namespace Chain{
	inl void dfs1(int u,int pre){
		sz[u]=1;
		rep(i,0,e[u].size()-1){
			int v=e[u][i];
			if(v==pre)continue;
			dep[v]=dep[u]+1;
			fa[v]=u;
			dfs1(v,u);
			sz[u]+=sz[v];
			if(sz[sn[u]]<sz[v])sn[u]=v;
		}
	}
	inl void dfs2(int u,int t){
		top[u]=t;
		dfn[u]=++cnt;
		rnk[cnt]=u;
		if(sn[u])dfs2(sn[u],t);
		rep(i,0,e[u].size()-1){
			int v=e[u][i];
			if(v==fa[u]||v==sn[u])continue;
			dfs2(v,v);
		}
	}
	inl int query_(int x,int y){
		int fx=top[x],fy=top[y],ans=inf;
		while(fx!=fy){
			if(dep[fx]<dep[fy]){swap(x,y);swap(fx,fy);}
			ans=min(ans,query(1,1,n,dfn[fx],dfn[x]));
			x=fa[fx];fx=top[x];
		}
		if(dfn[x]>dfn[y])swap(x,y);
		return min(ans,query(1,1,n,dfn[x],dfn[y]));
	}
}
using namespace Chain;
signed main(void){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	rep(i,1,n-1){
		int u,v;cin>>u>>v;
		e[u].push_back(v);e[v].push_back(u);
	}
	dfs1(1,0);dfs2(1,1);
	rep(i,1,n<<2)sum[i]=inf;
	while(q--){
		int op,x;cin>>op>>x;
		if(!op)update(1,1,n,dfn[x]);
		else {
			int tmp=query_(1,x);
			if(tmp==inf)cout<<"-1\n";
			else cout<<rnk[tmp]<<'\n';
		}
	}
}