求助点分治模板,代码在第四个点莫名WA……
查看原帖
求助点分治模板,代码在第四个点莫名WA……
128591
Refined_heart楼主2021/7/5 16:23
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
const int dyx=(1<<30);
const int dwttxdy=2;
inline int read(){
	int s=0,w=1;
	char Dyx=getchar();
	while(!isdigit(Dyx)){
		if(Dyx=='-')w=-1;
		Dyx=getchar();
	}
	while(isdigit(Dyx)){
		s=s*10-48+Dyx;
		Dyx=getchar();
	}
	return s*w;
} 
struct E{int nxt,to,dis;}e[MAXN];
int head[MAXN],n,m,tot,rt,mson[MAXN];
int siz[MAXN],Siz,ms;
bitset<MAXN>vis;
inline void add(int ddwt,int ddwtmz,int thevalue){
	e[++tot]=(E){head[ddwt],ddwtmz,thevalue};
	head[ddwt]=tot;
}
void Gr(int x,int fa){
	siz[x]=1;mson[x]=0;
	for(int i=head[x];i;i=e[i].nxt){
		int j=e[i].to;
		if(j==fa||vis[j])continue;
		Gr(j,x);siz[x]+=siz[j];
		if(siz[j]>mson[x])mson[x]=siz[j];
	}
	if(Siz-siz[x]>mson[x])mson[x]=Siz-siz[x];
	if(ms>mson[x])ms=mson[x],rt=x;
}
int t,tt,dis[MAXN],ans[500],dwt[500];
void getdis(int x,int fa,int d){
	dis[++t]=d;
	for(int i=head[x];i;i=e[i].nxt){
		int j=e[i].to;
		if(j==fa||vis[j])continue;
		getdis(j,x,d+e[i].dis);
	}
}
struct U{int v,num;}q[MAXN];
void solve(int x,int d,int fg){
	t=0;getdis(x,0,d);
	tt=0;sort(dis+1,dis+t+1);
	dis[0]=dyx; 
	for(int i=1;i<=t;++i){
		if(dis[i]!=dis[i-1])q[++tt].v=dis[i],q[tt].num=1;
		else q[tt].num++;
	}
	for(int i=1;i<=m;++i){
		int Dwt=1,dwtmz=tt;
		if(dwt[i]%dwttxdy==0){
			for(int dwtt=1;dwtt<=dwtmz;++dwtt){
				if(q[dwtt].v==dwt[i]/2)ans[i]+=(q[dwtt].num)*(q[dwtt].num-1)/2*fg;
			}
		}
		while(Dwt<=dwtmz){
			while(q[Dwt].v+q[dwtmz].v>dwt[i])--dwtmz;
			if(q[Dwt].v+q[dwtmz].v==dwt[i])ans[i]+=fg*q[Dwt].num*q[dwtmz].num;
			++Dwt;
		}
	}
}
void work(int x,int dwtwives){
	vis[x]=1;solve(x,0,1);
	for(int i=head[x];i;i=e[i].nxt){
		int j=e[i].to;
		if(vis[j])continue;
		solve(j,e[i].dis,-1);
		Siz=siz[j]<siz[x]?siz[j]:(dwtwives-siz[x]);
		ms=dyx;rt=0;Gr(j,0);work(rt,Siz);
	}
}
int main(){
// 	freopen("P2.in","r",stdin);
// 	freopen("dwtandhismzwillbeforever.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<n;++i){
		int Dowt=read(),Dowtmz=read(),theirvalue=read();
		add(Dowt,Dowtmz,theirvalue);
		add(Dowtmz,Dowt,theirvalue);
	}
	for(int i=1;i<=m;++i)dwt[i]=read();
	ms=dyx;rt=0;Siz=n;Gr(1,0);work(rt,n);
	for(int i=1;i<=m;++i){
		if(ans[i])puts("AYE");
		else puts("NAY");
	}
	return 0;
}
2021/7/5 16:23
加载中...