点分治求调,TLE on sub 3
查看原帖
点分治求调,TLE on sub 3
448884
快乐的大童楼主2023/8/14 12:04

rt

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0);
#define OTIE cout.tie(0);
#define PY puts("AYE")
#define PN puts("NAY")
#define PW puts("-1")
#define P__ puts("")
#define PU puts("--------------------")
#define popc __builtin_popcount
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)
#define reprange(a,b,c,d) for(int a=b;a<=c;a+=d)
#define perrange(a,b,c,d) for(int a=b;a>=c;a-=d)
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x);
//#define int long long
//#define int __int128
using namespace std;
inline int rd(){
	int x=0,f=1;int ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;
}
inline void write(int x,char ch='\0'){
	if(x<0){x=-x;putchar('-');}
	int y=0;char z[40];
	while(x||!y){z[y++]=x%10+48;x/=10;}
	while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
const int maxn=1e4+5;
int n,m;
vector<pii>G[maxn];
int rt;
int siz[maxn];
bool vis[maxn];
int q[maxn];
int ans[maxn];
struct node{
	int dis,bel;
	bool operator<(const node &p)const{
		return dis<p.dis;
	}
}a[maxn];
int cnt;
void dfs(int x,int y){
	siz[x]=1;
	for(auto i:G[x]){
		int u=i.fi;
		if(u==y) continue;
		dfs(u,x);siz[x]+=siz[u];
	}
}
void get_rt(int x,int y,int sum){
	bool flag=1;
	for(auto i:G[x]){
		int u=i.fi;
		if(u==y) continue;
		get_rt(u,x,sum);
		flag&=(siz[u]<=sum/2);
	}
	if(flag&&n-siz[x]<=sum/2) rt=x;
}
void get_dis(int x,int y,int dis,int bel){
	a[++cnt].bel=bel,a[cnt].dis=dis;
	for(auto i:G[x]){
		int u=i.fi;
		if(u==y) continue;
		get_dis(u,x,dis+i.se,bel);
	}
}
void calc(int x){
	cnt=0;
	a[++cnt].dis=0,a[cnt].bel=x;
	for(auto i:G[x]){
		if(vis[i.fi])continue;
		get_dis(i.fi,x,i.se,i.fi);
	}
	sort(a+1,a+cnt+1);
	rep(i,1,m){
		if(ans[i]) continue;
		int l=1,r=cnt;
		while(l<r){
			if(a[l].dis+a[r].dis==q[i]){
				if(a[l].bel!=a[r].bel){
					ans[i]=1;
					break;
				}else{
					if(a[r].dis==a[r-1].dis) r--;
					else l++;
				}
			}
			if(a[l].dis+a[r].dis<q[i]) l++;
			else r--;
		}
	}
}
void sol(int x){
	vis[x]=1;calc(x);
	for(auto i:G[x]){
		int u=i.fi;
		if(vis[u]) continue;
		dfs(u,0);get_rt(u,x,siz[u]);sol(rt);
	}
}
signed main(){
	n=rd(),m=rd();
	rep(i,1,n-1){
		int x=rd(),y=rd(),z=rd();
		G[x].push_back(mp(y,z)),G[y].push_back(mp(x,z));
	}
	rep(i,1,m)q[i]=rd();
	dfs(1,0);get_rt(1,0,n);sol(rt);
	rep(i,1,m){if(ans[i])PY;else PN;}
}
2023/8/14 12:04
加载中...