【点分治】洛谷 P3806 【模板】点分治1
2021-07-20 09:47:00 # ACM

题链

点分治分为四步：
$1.$找到树的重心
$2.$删除树的重心
$3.$处理经过重心的路径
$4.$处理重心的子树

详解来自BiliBili

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
using namespace std;
#define LL long long 
#define MAXN 10000009
#define MS 1000009

int n,m;
struct node{
	int to;
	LL val;
};
vector<node > vc[MS];
int ask[MS] ,ac[MS];
int rt,tr_size;
int sz[MS],w[MS];
int del[MS];
int dis[MS];
int dislist[MS],cntd;
int ext[MAXN];
queue<int > tmp;

void get_rt(int u,int f){ // 找重心 
	sz[u] = 1;
	w[u] = 0;
	for(auto &nb:vc[u]){
		int v = nb.to;
		if(v != f && !del[v]){
			get_rt(v,u);
			sz[u] += sz[v];
			w[u] = max(w[u],sz[v]); // 得到最大的子树大小 
		}
	}
	w[u] = max(w[u] ,tr_size-sz[u]); // 自己以及祖先的大小 
	if(w[u] < w[rt]) rt = u; // 更新重心 
}

void get_dis(int u,int f){
	dislist[++cntd] = dis[u]; // 记录所有距离 
	for(auto &nb:vc[u]){
		int v = nb.to;
		LL val = nb.val;
		if(v != f && !del[v]){
			dis[v] = dis[u] + val;
			get_dis(v,u);
		}
	}
}

void cal(int u){
	ext[0] = 1; // 标记权值 0 存在 
	for(auto &nb:vc[u]){
		int v = nb.to;
		LL val = nb.val;
		if(!del[v]){
			// 得到 v为根的子树到 u 的所有距离 
			cntd = 0;
			dis[v] = val;
			get_dis(v,u);
			// 处理询问 
			for(int i=1;i<=m;i++){
				for(int j=1;j<=cntd;j++){
					if(ask[i] >= dislist[j]){
						ac[i] |= ext[ ask[i] - dislist[j] ];
					}
				}
			}
			// 记录所有距离，标记该距离存在 
			for(int i=1;i<=cntd;i++){
				if(dislist[i] <= 1e7){
					ext[ dislist[i] ] = 1;
					tmp.push( dislist[i] );
				}
			}
		}
	}
	// 删除所有距离 
	ext[0] = 0;
	while(!tmp.empty()){
		ext[ tmp.front() ] = 0;
		tmp.pop();
	}
}

void divide(int u){
	del[u] = 1; // 删除重心 
	cal(u);		// 处理经过重心的路径 
	for(auto &nb:vc[u]){ // 对于每一个子树同样分治 
		int v = nb.to;
		if(!del[v]){
			// 找重心并分治 
			w[rt = 0] = tr_size = sz[v];
			get_rt(v,0);
			get_rt(rt,0);
			divide(rt);
		}
	}
}

void solve(){
	cin >> n >> m;
	for(int i=1;i<=n-1;i++){
		int u,v;
		LL val;
		cin >> u >> v >> val;
		vc[u].push_back({v,val});
		vc[v].push_back({u,val});  
	}
	for(int i=1;i<=m;i++){
		cin >> ask[i];
	}
	// 找到树的重心 
	w[rt = 0] = tr_size = n;
	get_rt(1,0);
	get_rt(rt,0);
	// 分治 
	divide(rt);
	
	for(int i=1;i<=m;i++){
		if(ac[i]) cout << "AYE\n";
		else cout << "NAY\n";
	}
}

int main(){
	ios::sync_with_stdio(false);
	int ce;
//	cin >> ce;
	ce = 1;
	while(ce--){
		solve();
	}
	
	return 0;
}
Prev
2021-07-20 09:47:00 # ACM
Next