QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387218#5020. 举办乘凉州喵,举办乘凉州谢谢喵linmouCompile Error//C++146.5kb2024-04-12 09:53:572024-04-12 09:53:57

Judging History

你现在查看的是最新测评结果

  • [2024-04-12 09:53:57]
  • 评测
  • [2024-04-12 09:53:57]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long//淇′话
#define pii pair <int,int>
#define lowbit(x) (-x&x)
#define lson (p<<1)
#define rson (p<<1|1)
using namespace std;
#define read() (red<int>())
template<typename T>inline T red(){T x=0;bool f=false;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=true;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?-x:x;}
template<typename T>inline void write(T x){if(x<0){putchar('-');x=-x;}if(x/10)write(x/10);putchar((x%10)^48);return;}
const int N=2e5+5;
int n,q;
int cnt=-1;
int first[N],next_[N<<1],to[N<<1];
inline void add(int a,int b){
	++cnt;
	next_[cnt]=first[a];
	first[a]=cnt;
	to[cnt]=b;
	return ;
} 
inline void add_e(int a,int b){
	add(a,b);
	add(b,a);
	return ;
}
struct ASK{
	int d;
	int num,ty;
	ASK(int D,int Num,int Ty){
		d=D;num=Num;ty=Ty;
	}
};
std::vector<ASK>ask[N];
int ans[N];
int g,minn;
int del[N];
int sizg[N],fag[N];
void get_siz(int x,int father){
	fag[x]=father;
	sizg[x]=1;
	for(int i=first[x];i!=-1;i=next_[i]){
		int v=to[i];
		if(v==fag[x])continue;
		if(del[v])continue;
		get_siz(v,x);
		sizg[x]+=sizg[v];
	}
	return ;
}
void get_g(int x,int Siz){
	int maxn=Siz-sizg[x];
	for(int i=first[x];i!=-1;i=next_[i]){
		int v=to[i];
		if(v==fag[x])continue;
		if(del[v])continue;
		maxn=std::max(maxn,sizg[v]);
		get_g(v,Siz);
	}
	if(maxn<minn){
		minn=maxn;g=x;
	}
	return ;
}
int dis[N];
int tmpdis[N];
int cntt;
void get_dis(int x,int fa){
	if(x<=n)tmpdis[++cntt]=dis[x];
	for(int i=first[x];i!=-1;i=next_[i]){
		int v=to[i];
		if(v==fa)continue;
		if(del[v])continue;
		dis[v]=dis[x]+1;
		get_dis(v,x);
	}
	return ;
}
inline int get_minn(int d){
	if(d<tmpdis[1])return 0;
	if(d>=tmpdis[cntt])return cntt;
	return std::upper_bound(tmpdis+1,tmpdis+cntt+1,d)-tmpdis-1;
}
void update_ans(int x,int ty,int fa){
	for(int i=0;i<ask[x].size();++i){
		int w=get_minn(ask[x][i].d-dis[x]);
		if((ty==1&&ask[x][i].ty==1)||(ty==-1&&ask[x][i].ty==-1)){
			ans[ask[x][i].num]+=w;
		}
		else ans[ask[x][i].num]-=w;
	}
	for(int i=first[x];i!=-1;i=next_[i]){
		int v=to[i];
		if(v==fa)continue;
		if(del[v])continue;
		update_ans(v,ty,x);
	}
}
void get_ans(int x,int d,int ty){
	cntt=0;
	dis[x]=d;
	get_dis(x,0);
	std::sort(tmpdis+1,tmpdis+cntt+1);
	update_ans(x,ty,0);
}
const int inf=320051113;
void work(int x){
	minn=inf;
	get_siz(x,0);
	get_g(x,sizg[x]);
	x=g;
	get_ans(x,0,1);
	del[x]=1;
	for(int i=first[x];i!=-1;i=next_[i]){
		int v=to[i];
		if(del[v])continue;
		get_ans(v,1,-1);
		work(v);
	}
	return ;
}
int f[21][N];
int fa[N],dep[N],siz[N],hson[N],topn[N];
std::vector<int>bigtopn;
std::vector<int>leaves;
void dfs1(int x,int father){
	fa[x]=father;
	f[0][x]=fa[x];
	dep[x]=dep[fa[x]]+1;
	siz[x]=1;
	for(int i=first[x];i!=-1;i=next_[i]){
		int v=to[i];
		if(v==fa[x])continue;
		dfs1(v,x);
		siz[x]+=siz[v];
		if(siz[v]>siz[hson[x]]){
			hson[x]=v;
		}
	}
	if(siz[x]==1){
		leaves.push_back(x);
	}
	return ;
}
void dfs2(int x,int top){
	if(x==top){
		bigtopn.push_back(x);
	}
	topn[x]=top;
	if(hson[x])dfs2(hson[x],top);
	for(int i=first[x];i!=-1;i=next_[i]){
		int v=to[i];
		if(v==fa[x])continue;
		if(v==hson[x])continue;
		dfs2(v,v);
	}
	return ;
}
inline void init(){
	for(int i=1;i<=20;++i){
		for(int j=1;j<=n;++j){
			f[i][j]=f[i-1][f[i-1][j]];
		}
	}
	return ;
}
inline int get_lca(int x,int y){
	if(dep[x]<dep[y])std::swap(x,y);
	for(int i=20;i>=0;--i){
		if(dep[f[i][x]]>=dep[y])x=f[i][x];
	}
	if(x==y)return x;
	for(int i=20;i>=0;--i){
		if(f[i][x]!=f[i][y]){
			x=f[i][x];y=f[i][y];
		}
	}
	return f[0][x];
}
std::vector<ASK>bigpaskfa[N];
std::vector<ASK>bigpaskson[N];
inline void add_ask(int x,int d,int ty,int num){
	while(x){
		bigpaskfa[x].push_back(ASK(d,num,ty));
		x=topn[x];
		x=fa[x];
	} 
	return ;
}
inline void add_big_son(int x,int lca,int d,int num){
	while(dep[x]>dep[lca]){
		if(hson[x])bigpaskson[hson[x]].push_back(ASK(d-1,num,1));
		x=topn[x];
		if(dep[fa[x]]>dep[lca]){
			bigpaskson[x].push_back(ASK(d-1,num,-1));
		}
		x=fa[x];
	}
	return ;
}
int tree[N];
int stax[N],stav[N];
int r;
inline void add_v(int x,int v,int t=0){
	if(t==0){
		++x;
		++r;
		stax[r]=x;stav[r]=v;
	}
	for(;x<=n+1;x+=lowbit(x)){
		tree[x]+=v;
	}
	return ;
}
inline int get_v(int x){
	++x;
	if(x<=0)return 0;
	int ans=0;
	for(;x;x-=lowbit(x)){
		ans+=tree[x];
	}
	return ans;
}
inline void clear_tree(){
	while(r){
		add_v(stax[r],-stav[r],1);--r;
	}
	return ;
}
void add_x(int x,int dis){
	add_v(dis,1);
	for(int i=first[x];i!=-1;i=next_[i]){
		int v=to[i];
		if(v==fa[x])continue;
		add_x(v,dis+1);
	}
	return ;
}
void askfa(int x){
	if(!x)return ;
	for(int i=first[x];i!=-1;i=next_[i]){
		int v=to[i];
		if(v==fa[x])continue;
		if(v==hson[x])continue;
		add_x(v,1);
	}
	for(int i=0;i<bigpaskfa[x].size();++i){
		ans[bigpaskfa[x][i].num]+=bigpaskfa[x][i].ty*get_v(bigpaskfa[x][i].d);
	}
	askfa(hson[x]);
	return ;
}
inline void work_askfa(){
	for(int i=0;i<bigtopn.size();++i){
		askfa(bigtopn[i]);
		clear_tree();
	}
	return ;
}
void askson(int x,int height){
	if(!x)return ;
	for(int i=first[x];i!=-1;i=next_[i]){
		int v=to[i];
		if(v==fa[x])continue;
		if(v==hson[x])continue;
		add_x(v,dep[v]);
	}
	add_v(dep[x],1);
	for(int i=0;i<bigpaskson[x].size();++i){
		ans[bigpaskson[x][i].num]+=bigpaskson[x][i].ty*get_v(dep[x]+bigpaskson[x][i].d);
	}
	if(topn[x]==x)return ;
	askson(fa[x],height+1);
	return ;
}
inline void work_askson(){
	for(int i=0;i<leaves.size();++i){
		askson(leaves[i],0);
		clear_tree();
	}
	return ;
}
inline void add_chain(int x,int lca,int d,int num){
	add_big_son(x,lca,d,num);
	add_ask(x,d,1,num);
	add_ask(lca,d,-1,num);
	for(int i=20;i>=0;--i){
		if(dep[f[i][x]]>dep[lca])x=f[i][x];
	}
	bigpaskson[x].push_back(ASK(d-1,num,-1));
	return ;
} 
int main(){
//	freopen("meow.in","r",stdin);
//	freopen("meow.out","w",stdout);
	memset(first,-1,sizeof(first));
	n=read();
	for(int i=1;i<n;++i){
		int a=read(),b=read(); 
		add_e(a,b);
	}
	dfs1(1,0);
	dfs2(1,1);
	init();
	q=read();
	for(int i=1;i<=q;++i){
		int x=read(),y=read(),d=read();
		if(dep[x]<dep[y])std::swap(x,y);
		int lca=get_lca(x,y);
		ans[i]=dep[x]+dep[y]-dep[lca]-dep[lca];
		ask[lca].push_back(ASK(d,i,1));
		
		if(y==lca){
			if(x!=lca)add_chain(x,lca,d,i);
		}
		if(x!=lca&&y!=lca){
			add_chain(x,lca,d,i);
			add_chain(y,lca,d,i);
		}
	}
	work(1);
	work_askfa();
	work_askson();
	for(int i=1;i<=q;i++){
		write(ans[i]);
		puts("");
	}
	return 0;
}

Details

cc1plus: error: ‘::main’ must return ‘int’