求助点分治模板 全WA
查看原帖
求助点分治模板 全WA
357163
shyr楼主2022/7/20 19:03
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int read(){
    int x = 0,f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

inline void write(int x)
{
    char F[200];
    int tmp = x > 0 ? x : -x;
    if(x<0) putchar('-');
    int cnt = 0;
	while(tmp > 0){
        F[cnt++] = tmp%10+'0';
        tmp /= 10;
    }
    while(cnt > 0) putchar(F[--cnt]);
    putchar('\n');
}
const int N = 10005, MaxN = 100000005;
int n, m, u, v, w, Q[105];
int tmp[MaxN], ans[MaxN];//tmp 存所求子树到当前重心的距离
//can 存之前子树到当前重心的距离
int siz[N], vis[N];// sz存节点及子树大小 vis存是否访问过
int maxp[N];//存最大子树的大小 
int tot, rt, dis[N];//dis存到当前重心的距离 
int q[MaxN], ynn[N];//队列辅助清空 ynn记录答案 
vector< pair<int, int> > d[10005]; 
namespace _std{
	void predfz(int x, int fa){
		siz[x] = 1; maxp[x] = 0;
		for(int i = 0; i < d[x].size(); ++i){
			int y = d[x][i].first;
			if(y == fa || vis[y]) return ;
			predfz(y, x);
			siz[x] += siz[y];
			maxp[x] = max(maxp[x], siz[y]);
		}
		maxp[x] = max(maxp[x], tot - siz[x]);
		if(maxp[x] < maxp[rt]) rt = x;
	}
	void cal(int x);
	void solve(int x){
		vis[x] = ans[0] = 1; cal(x);
		for(int i = 0; i < d[x].size(); ++i){
			int y = d[x][i].first;
			if(vis[y]) continue;
			tot = siz[y];
			maxp[0] = MaxN;
			rt = 0;
			predfz(y, 0);
			solve(rt);
		}
	} 
	void update(int x, int fa){
		tmp[++tmp[0]] = dis[x];
		for(int i = 0; i < d[x].size(); ++i){
			int y = d[x][i].first;
			int val = d[x][i].second;
			if(vis[y] || y == fa) continue;
			dis[y] = dis[x] + val;
			update(y, x);
		}
		
	}
	void cal(int x){
		int p = 0;
		for(int i = 0; i < d[x].size(); ++i){
			int y = d[x][i].first, val = d[x][i].second;
			if(vis[y]) continue;
			tmp[0] = 0; dis[y] = val;
			update(y, x);
			for(int k = tmp[0]; k; --k){
				for(int j = 1; j <= m; ++j){
					if(Q[j] >= tmp[k]){
						ynn[j] |= ans[Q[j] - tmp[k]];
					}
				}
			}
			for(int k = tmp[0]; k; --k) q[++p] = tmp[k], ans[tmp[k]] = 1;
		}
		for(int i = 1; i <= p; ++i) ans[q[i]] = 0;
	}
}
int main(){
	n = read(), m = read();
	for(int i = 1; i < n; ++i){
		u = read(), v = read(), w = read();
		d[u].push_back(make_pair(v, w));
		d[v].push_back(make_pair(u, w));
	}
	for(int i = 1; i <= m; ++i) Q[i] = read();
	maxp[0] = n;
	rt = 0;
	tot = n;
	_std::predfz(1, 0); 
	_std::solve(rt); 
	for(int i = 1; i <= m; ++i){
		if(ynn[i]) printf("AYE\n");
		else printf("NAY\n");
	}
	return 0;
}

2022/7/20 19:03
加载中...