CF940F Machine Learning (点分治）

做法

按照套路 我们分三种情况讨论

如果 这条路径在一个子树 直接 递归处理
如果 在不同 子树 我们进行 合并 mp1 和 mp2
如果 有一个点是重心 那么我们就可以 直接在 dfs的时候去统计

#include 
using namespace  std;
#define  int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define pb  push_back
#define inf 1ll<<62
#define endl "\n"
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define de_bug(x) cerr << #x << "=" << x << endl
#define all(a) a.begin(),a.end()
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--)
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
const int M = 1e6 + 10;
int n, k;
int ans[N], cnt, idx2;
int h[N], e[M], ne[M];
int vis[N];
int m;
int p[N];
int q[N];
int a[N];
int dp[N];


map<int, int>mp1;
map<int, int>mp2;

void add(int a, int b) {
	e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}
int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}
void get_dis(int u, int fa, int tmp) {
	if(vis[u] )return ;
	ans[tmp]++;
	mp1[tmp]++;
	for(int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];
		if(v == fa)continue;
		get_dis(v, u, __gcd(tmp, a[v]));
	}
}
int  get_sz(int u, int fa) {
	if(vis[u])return 0;
	int ans = 1;
	for(int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];
		if(v == fa)continue;
		ans += get_sz(v, u);
	}
	return ans;
}
int  get_wc(int u, int fa, int tot, int &wc ) {
	if(vis[u])return 0;
	int sum = 1;
	int ma = 0;
	for(int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];
		if(v == fa)continue;
		int t = get_wc(v, u, tot, wc);
		ma = max(ma, t);
		sum += t;
	}
	ma = max(ma, tot - sum);
	if(ma <= tot / 2) {
		wc = u;
	}
	return sum;
}
void calc(int u) {
	if(vis[u])return ;
	get_wc(u, -1, get_sz(u, -1), u);
	vis[u] = 1;
	ans[a[u]]++;


	for(int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];
		if(vis[v])continue;
		mp1.clear();
		get_dis(v, u, __gcd(a[u], a[v]));
		for(auto x : mp1)
			for(auto y : mp2) {
				//	cout<<11111;
				int t = __gcd(x.fi, y.fi);
				ans[t] += 1ll * x.se * y.se;
			}
		for(auto x : mp1) {
			mp2[x.fi] += x.se;
		}
		//	de_bug(mp2[1]);
	}
	mp2.clear();

	for(int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];
		calc(v);
	}

}
void solve() {
	cin >> n ;
	for(int i = 1; i <= n; i++)cin >> a[i];
	memset(h, -1, sizeof(h));
	fer(i, 1, n - 1) {
		int a, b, c;
		cin >> a >> b ;
		add(a, b);
		add(b, a);
	}
	calc(1);
	for(int i = 1; i <= 200000; i++) {
		if(ans[i]) {
			cout << i << " " << ans[i] << endl;
		}
	}
}
signed main() {
	IOS;
	int _ = 1;
	//cin>>_;
	while( _-- )
		solve();
}


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
135
136