1 条题解

  • 0
    @ 2023-11-2 20:50:41
    #define ll long long
    using namespace std;
    const int N=1e4+5;
    int n;
    struct node{int v,w;};
    vector<node>g[N];
    bool vis[N];
    int get_size(int u,int p)//返回子树的结点数
    {
    	if(vis[u])return 0;
    	int sum=1;
    	for(auto v:g[u])
    		if(v.v!=p)
    			sum+=get_size(v.v,u);
    	return sum;
    }
    int cal_wc(int u,int fa,int tot,int &wc)//寻找重心 重心为wc即时修改 tot为连通块结点总数
    {
    	if(vis[u])
    		return 0;
    	int sum=1,ms=0;//ms为子树中最大的子树的结点数 sum为所有子树的结点总和
    	for(auto v:g[u])
    	{
    		if(v.v!=fa)
    		{
    			int tmp=cal_wc(v.v,u,tot,wc);//子树结点数
    			sum+=tmp;
    			ms=max(ms,tmp);
    		}
    	}
    	ms=max(ms,tot-sum);
    	if(ms<=tot/2)wc=u;
    	return sum;
    }
    bool used[10000005];
    int maxn=0;
    vector<int>cnt1;
    vector<int>cnt2;
    void dfs2(int u,int fa,int step)
    {
    	if(vis[u])
    		return;
    	if(step>10000000)
    		return;
    	used[step]=true;
    	cnt2.push_back(step);
    	for(auto v:g[u])
    		if(v.v!=fa)
    			dfs2(v.v,u,step+v.w);
    }
    
    void dfs(int u)//寻找重心且往重心的子树递归
    {
    	if(vis[u])
    		return;
    	cal_wc(u,-1,get_size(u,-1),u);//寻找该子树重心
    	//进行处理
    	cnt1.clear();
    	for(auto v:g[u])
    	{
    		cnt2.clear();
    		dfs2(v.v,u,v.w);
    		for(auto i:cnt1)
    			for(auto j:cnt2)
    				if(i+j>10000000)
    					continue;
    				else
    					used[i+j]=true;
    		for(auto i:cnt2)
    			cnt1.push_back(i);
    	}
    	
    	vis[u]=true;//标记重心
    	for(auto v:g[u])
    		dfs(v.v);//往下递归
    }
    int main()
    {
    	int T;
    	scanf("%d%d",&n,&T);
    	for(int i=1;i<n;i++)
    	{
    		int u,v,w;
    		scanf("%d%d%d",&u,&v,&w);
    		g[u].push_back({v,w});
    		g[v].push_back({u,w});
    	}
    	dfs(1);
    	while(T--)
    	{
    		int x;
    		scanf("%d",&x);
    		if(used[x])
    			puts("YES");
    		else
    			puts("NO");
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    24
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    25
    已通过
    3
    上传者