CODECHEF LUNCHTIME37

codechef Programming

これやってたらSRMレジりミスった.

LCOLLIS:やるだけ
OMWG:O(1)
SQNUMBF: 100個のlong longの積が4以上の平方数で割れるかどうか.素数p^2のみ考えれば良い.pが2つの整数にまたがっている場合は,gcdを取ればpが出てくるのでわかる.1つの整数の場合は,10^6まで全部試したら,残りが平方数になっているしか望みがないのでsqrtとって判定.

TRAVTREE:木があります.pathが順に与えられるので,それぞれ「これまでのpathのうちこのpathと交わっているのは何個」を答えてください.N,Q≤2e5くらい.

この前のRCCでも面倒要素としてあったpathの交わり系だけど,(一点でも)交わるのは3通りに場合分け出来る.
pathをa-b,c-dとしてlcaをx,yとすると,

  1. xがc-dに含まれる
  2. yがa-bに含まれる
  3. 上の両方(これはx=yと同値)

上に向かう途中で分岐することはないのでそれはそう.
今回はそれぞれで数え上げれば良くて,今見てるのをc-dの方とすると,
1:クエリはpathのsum,更新はpointに+1
2:クエリはpointのvalue,更新はpathに+1
3:1を使えばわかる

今回は操作に逆元があるのでEulerTourが使える.
EulerTour + LCA + segtree で二つのpathに分解してそれぞれやればOK.

ほとんどライブラリ

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

const int MAX_V=200000;
const int LOGV=18;
int par[MAX_V][LOGV],depth[MAX_V];
vector<int> G[MAX_V];
void dfs(int v,int p){
	if(p<0) depth[v]=0;
	else depth[v]=depth[p]+1;
	par[v][0]=p;
	for(int u:G[v]){
		if(u!=p) dfs(u,v);
	}
}
void genlca(int N){
	dfs(0,-1);
	for(int i=1;i<LOGV;i++){
		rep(v,N){
			if(par[v][i-1]==-1) par[v][i]=-1;
			else par[v][i]=par[par[v][i-1]][i-1];
		}
	}
}
int lca(int u,int v){
	if(depth[u]<depth[v]){
		swap(u,v);
	}
	int d=depth[u]-depth[v];
	rep(i,LOGV){
		if((d>>i)&1) u=par[u][i];
	}
	if(u==v) return u;
	for(int i=LOGV-1;i>=0;i--){
		if(par[u][i]!=par[v][i]){
			u=par[u][i];
			v=par[v][i];
		}
	}
	return par[v][0];
}

int I;
int id[MAX_V*2];
bool in[MAX_V*2];
int v2id[MAX_V][2];	//[0]:in [1]:out
void eulertour(int v,int p){
	id[I]=v,in[I]=1,v2id[v][0]=I,I++;
	for(int u:G[v]) if(u!=p) eulertour(u,v);
	id[I]=v,in[I]=0,v2id[v][1]=I,I++;
}


struct segtreeRsumPadd{
	static const int N=1<<19;
	int seg[N*2];
	
	segtreeRsumPadd(){
		rep(i,N*2) seg[i]=0;
	}
	void add(int x,int v){
		x+=N;
		while(x){
			seg[x]+=v;
			x/=2;
		}
	}
	int sum(int a,int b,int l=0,int r=N,int k=1){
		if(b<=l||r<=a) return 0;
		if(a<=l&&r<=b) return seg[k];
		return sum(a,b,l,(l+r)/2,k*2)+sum(a,b,(l+r)/2,r,k*2+1);
	}
}sega;
struct segtreePsumRadd{
	static const int N=1<<19;
	int seg[N*2];
	
	segtreePsumRadd(){
		rep(i,N*2) seg[i]=0;
	}
	int val(int x){
		x+=N;
		int ret=0;
		while(x){
			ret+=seg[x];
			x/=2;
		}
		return ret;
	}
	void add(int a,int b,int v,int l=0,int r=N,int k=1){
		if(b<=l||r<=a) return;
		if(a<=l&&r<=b){seg[k]+=v;return;}
		add(a,b,v,l,(l+r)/2,k*2),add(a,b,v,(l+r)/2,r,k*2+1);
	}
}segb;

int main(){
	int N,Q;
	cin>>N;
	rep(i,N-1){
		int a,b;
		scanf("%d%d",&a,&b);
		a--,b--;
		G[a].pb(b);
		G[b].pb(a);
	}
	genlca(N);
	eulertour(0,-1);
	cin>>Q;
	rep(tt,Q){
		int a,b;
		scanf("%d%d",&a,&b);
		a--,b--;
		int w=lca(a,b);
		int A=sega.sum(v2id[w][0],v2id[a][0]+1);
		int B=sega.sum(v2id[w][0],v2id[b][0]+1);
		int C=sega.sum(v2id[w][0],v2id[w][0]+1);
		int D=segb.val(v2id[w][0])-segb.val(v2id[w][1]);
//		show(A);
//		show(B);
//		show(C);
//		show(D);
		int ret=A+B+D-C*2;
		printf("%d\n",ret);
		sega.add(v2id[w][0],1);
		sega.add(v2id[w][1],-1);
		segb.add(v2id[w][0],v2id[a][0]+1,1);
		segb.add(v2id[w][0],v2id[b][0]+1,1);
		segb.add(v2id[w][0],v2id[w][0]+1,-1);
	}
}