luoguP3806 【模板】点分治1

逃离我推掉我的手 2021-11-16 05:26 284阅读 0赞

#include<bits/stdc++.h>
    #define setIO(s) freopen(s".in","r",stdin) 
    #define maxn 10004  
    #define inf 10000003
    using namespace std;
    int edges,n,Q,sn,root,tl; 
    bool is[inf]; 
    int hd[maxn],to[maxn<<1],nex[maxn<<1],val[maxn<<1];  
    int answer[maxn], que[200], vis[maxn], f[maxn], siz[maxn], dep[maxn], mine[inf], dis1[maxn];        
    inline void add(int u,int v,int c)
    {
    	nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c; 
    } 
    void Getroot(int u,int fa)
    {
    	f[u]=0, siz[u]=1; 
    	for(int i=hd[u];i;i=nex[i])
    	{
    		int v=to[i]; 
    		if(vis[v]||v==fa) continue; 
    		Getroot(v,u), siz[u]+=siz[v]; 
    		f[u]=max(f[u], siz[v]); 
    	}
    	f[u]=max(f[u], sn-siz[u]); 
    	if(f[u]<f[root]) root=u;     
    }
    inline void getdis(int u,int fa,int d)
    {      
    	dis1[++tl] = d;  
    	for(int i=hd[u];i;i=nex[i])
    	{ 
    		int v=to[i]; 
    		if(v==fa||vis[v]) continue; 
    		getdis(v, u, d + val[i]);   
    	}
    }
    inline void calc(int u)
    {
    	tl=0; 
    	mine[0]=1;        
    	for(int i=hd[u];i;i=nex[i])
    	{
    		int v=to[i];
    		if(vis[v]) continue; 
    		int pdl=tl; 
    		getdis(v, u, val[i]); 
    		for(int j=pdl+1;j<=tl;++j) 
    			for(int o=1;o<=Q;++o)
    			{
    				if(que[o]>=inf||que[o] < dis1[j]) continue;  
    				is[que[o]]|=mine[que[o]-dis1[j]];     
    			}   
    		for(int j=pdl+1;j<=tl;++j) mine[dis1[j]]=1; 
    	} 
        for(int i=1;i<=tl;++i) mine[dis1[i]]=0;      
    }
    void solve(int u)
    {
    	int i,v;
    	vis[u]=1;    
    	calc(u);     
    	for(i=hd[u];i;i=nex[i])
    	{
    		v=to[i]; 
    		if(vis[v]) continue;   
    		root=0,sn=siz[v],Getroot(v, u); 
    		solve(root);      
    	}
    }
    int main()
    {
    	int i,j; 
    	// setIO("input"); 
    	scanf("%d%d",&n,&Q);
    	for(i=1;i<n;++i)
    	{
    		int u,v,c; 
    		scanf("%d%d%d",&u,&v,&c); 
    		add(u,v,c), add(v,u,c);   
    	}
    	for(i=1;i<=Q;++i) scanf("%d",&que[i]);  
    	sn=n,f[0]=maxn,Getroot(1,0),solve(root);  
    	for(i=1;i<=Q;++i) if(is[que[i]]) puts("AYE"); else puts("NAY");   
    	return 0; 
    }

转载于:https://www.cnblogs.com/guangheli/p/11103235.html