[国家集训队 2011] 公交路线 - cstdio - 143527

记录编号	143527	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2011] 公交路线	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	7.148 s
提交时间	2014-12-15 17:58:25	内存使用	47.05 MiB
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
const int SIZEN=200010;//防止DFSlen爆掉统统乘二,任性!
const int SIZELG=20;
class BIT{
public:
	int n;
	int s[SIZEN];
	#define lowbit(x) ((x)&(-x))
	void clear(int n_){
		n=n_;
		memset(s,0,sizeof(s));
	}
	void add(int x,int t){
		for(;x<=n;x+=lowbit(x)) s[x]+=t;
	}
	int presum(int x){
		int ans=0;
		for(;x;x-=lowbit(x)) ans+=s[x];
		return ans;
	}
	int sum(int x,int y){
		return presum(y)-presum(x-1);
	}
};
int log_2(int x){
	int ans=-1;
	while(x){x>>=1;ans++;}
	return ans;
}
int N,PN,Q;//节点数,路径数,询问数
int ans[SIZEN];
bool sure[SIZEN];
int S[SIZEN],T[SIZEN];
int A[SIZEN],B[SIZEN];
int stepup[SIZEN][SIZELG];
vector<int> c[SIZEN];
int DFSlis[SIZEN],DFSlen=0;
int dfn[SIZEN],end[SIZEN];//dfn是首次,end是最后一次
int depth[SIZEN];
int father[SIZEN];
int ST[SIZEN][SIZELG];
void STLCA_Prepare(void){
	int m=log_2(DFSlen);
	for(int i=1;i<=DFSlen;i++) ST[i][0]=DFSlis[i];
	for(int j=1;j<=m;j++){
		for(int i=1;i<=DFSlen;i++){
			if(i+(1<<j)-1>DFSlen) continue;
			int x=ST[i][j-1],y=ST[i+(1<<(j-1))][j-1];
			ST[i][j]=depth[x]<depth[y]?x:y;
		}
	}
}
int LCA(int a,int b){
	int l=dfn[a],r=dfn[b];
	if(l>r) swap(l,r);
	int m=log_2(r-l+1);
	int x=ST[l][m],y=ST[r-(1<<m)+1][m];
	return depth[x]<depth[y]?x:y;
}
void DFS(int x){
	DFSlen++;dfn[x]=end[x]=DFSlen;DFSlis[DFSlen]=x;
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i];
		if(u==father[x]) continue;
		father[u]=x;depth[u]=depth[x]+1;
		DFS(u);
		DFSlis[++DFSlen]=x;end[x]=DFSlen;
	}
}
class Grand_Path{
public:
	int u,v;//u是v的祖先
};
bool operator < (Grand_Path a,Grand_Path b){
	if(depth[a.u]==depth[b.u]) return depth[a.v]<depth[b.v];
	return depth[a.u]<depth[b.u];
}
int Walk_Up(int &a,int g){//从a走到"g的前一步"
	int ans=0;
	int m=log_2(depth[a]);
	while(true){
		if(stepup[a][0]==a) break;
		int j=m;while(j>=0&&depth[stepup[a][j]]<=depth[g]) j--;
		if(j<0) break;
		ans+=(1<<j);
		a=stepup[a][j];
	}
	return ans;
}
void Deal_Cross(void){
	static vector<int> point[SIZEN];
	static vector<int> quest[SIZEN];
	static int cnt[SIZEN]={0};
	for(int i=1;i<=Q;i++){
		if(sure[i]) continue;
		quest[dfn[A[i]]-1].push_back(-i);
		quest[end[A[i]]].push_back(i);
	}
	for(int i=1;i<=PN;i++){
		point[dfn[S[i]]].push_back(dfn[T[i]]);
		point[dfn[T[i]]].push_back(dfn[S[i]]);
	}
	static BIT T;T.clear(DFSlen);
	for(int i=1;i<=DFSlen;i++){
		for(int j=0;j<point[i].size();j++)
			T.add(point[i][j],1);
		for(int j=0;j<quest[i].size();j++){
			int k=abs(quest[i][j]);
			int now=T.sum(dfn[B[k]],end[B[k]]);
			if(quest[i][j]<0) cnt[k]-=now;
			else cnt[k]+=now;
		}
	}
	for(int i=1;i<=Q;i++)
		if(!sure[i]&&cnt[i]==0) ans[i]++;
}
void Pre_Deal(int k){
	if(depth[A[k]]>depth[B[k]]) swap(A[k],B[k]);//A较高
	int &a=A[k],&b=B[k];
	if(a==b){
		ans[k]=0;
		sure[k]=true;
		return;
	}
	int g=LCA(a,b);
	if(g==a){
		ans[k]=Walk_Up(b,a);
		sure[k]=true;
		if(stepup[b][0]==b) ans[k]=-1;
		return;
	}
	ans[k]=Walk_Up(a,g)+Walk_Up(b,g);
	if(stepup[a][0]==a||stepup[b][0]==b) ans[k]=-1,sure[k]=true;
}
void Process(void){
	for(int i=1;i<=Q;i++) Pre_Deal(i);
	Deal_Cross();
	for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
}
void Prepare(void){
	STLCA_Prepare();
	static vector<Grand_Path> path;
	for(int i=1;i<=PN;i++){
		int g=LCA(S[i],T[i]);
		path.push_back((Grand_Path){g,S[i]});
		path.push_back((Grand_Path){g,T[i]});
	}
	sort(path.begin(),path.end());
	for(int i=0;i<path.size();i++){
		int x=path[i].v;
		while(!stepup[x][0]){
			stepup[x][0]=path[i].u;
			if(x==path[i].u) break;
			else x=father[x];
		}
	}
	for(int i=1;i<=N;i++) if(!stepup[i][0]) stepup[i][0]=i;
	int m=log_2(N);
	for(int j=1;j<=m;j++)
		for(int i=1;i<=N;i++)
			stepup[i][j]=stepup[stepup[i][j-1]][j-1];
}
void Read(void){
	scanf("%d%d%d",&N,&PN,&Q);
	int a,b;
	for(int i=1;i<N;i++){
		scanf("%d%d",&a,&b);
		c[a].push_back(b);
		c[b].push_back(a);
	}
	for(int i=1;i<=PN;i++) scanf("%d%d",&S[i],&T[i]);
	for(int i=1;i<=Q;i++) scanf("%d%d",&A[i],&B[i]);
}
int main(){
	freopen("nt2011_bus.in","r",stdin);
	freopen("nt2011_bus.out","w",stdout);
	Read();
	depth[1]=1;
	DFS(1);
	Prepare();
	Process();
	return 0;
}