## Du Lịch

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5+5;
vector<int> adj[N];
int n,k;
int a[N];
struct Data {
	int val,pos;
	Data operator + (const Data &o) const {
		if (val > o.val) {
			return {val,pos};
		}
		else if (val == o.val &&  pos < o.pos) return {val,pos};
		else return o;
	}
}node[4*N];
int lazy[4*N];
int pos[N],ti[N],to[N],cnt,lv[N];
void build (int id, int l, int r) {
	if (l == r) {
		node[id] = {a[pos[l]]-lv[pos[l]],pos[l]};
		return;
	}
	int mid = (r+l) >> 1;
	build (2*id,l,mid);
	build (2*id+1,mid+1,r);
	node[id] = node[2*id] + node[2*id+1] ;
}
void down (int id) {
	node[2*id].val += lazy[id];
	node[2*id+1].val += lazy[id];
	lazy[2*id] += lazy[id];
	lazy[2*id+1]+= lazy[id];
	lazy[id] = 0;
}
void update (int id, int l, int r, int u, int v, int val) {
	if (l > v || r < u) return;
	if (l>=u&&r<=v ){
		node[id].val += val;
		lazy[id] += val;
		return;
	}
	if (l!=r)down(id);
	int mid = (r+l) >> 1;
	update (2*id,l,mid,u,v,val);
	update (2*id+1,mid+1,r,u,v,val);
	node[id] = node[2*id]+node[2*id+1];
}
int inf = -1e18;
Data get (int id ,int l, int r, int u, int v) {
	if (l > v || r < u) return {inf,0};
	if (l>=u&&r<=v) {
		return node[id];
	}
	if (l!=r) down (id);
	int mid = (r+l) >> 1;
	return get (2*id,l,mid,u,v) + get (2*id+1,mid+1,r,u,v);
}
void init (int u, int p) {
	ti[u] = ++cnt;
	pos[cnt] = u;
	for (int i=0; i<adj[u].size(); i++) {
		int v = adj[u][i];
		if (v == p) continue;
		lv[v] = lv[u] + 1;
		init(v,u);
	} 
	to[u] = cnt;
}
int go[N];
void dfs (int u, int p){
//	update (1,1,n,ti[u],ti[u],-a[u]);
	update (1,1,n,ti[u],to[u],1);
	update (1,1,n,1,ti[u]-1,-1);
	update (1,1,n,to[u]+1,n,-1);
	Data tmp = get(1,1,n,1,ti[u]-1) + get (1,1,n,ti[u]+1,n);
	go[u] = tmp.pos;
//	cout << u  << ' ' << go[u] << '\n';
//	cout << u << ' ' << node[1].val << ' ' << node[1].pos << '\n';
	for (int i=0; i<adj[u].size(); i++) {
		int v = adj[u][i];
		if (v == p) continue;
		dfs(v,u);
	}
//	update (1,1,n,ti[u],ti[u],a[u]);
	update (1,1,n,ti[u],to[u],-1);
	update (1,1,n,1,ti[u]-1,1);
	update (1,1,n,to[u]+1,n,1);
}
int vis[N];
vector<int> g;
signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;
	for (int i=1; i<=n; i++) cin >> a[i];
	for (int i=1; i<n; i++) {
		int u,v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	} 
	init(1,1);
	build (1,1,n);
	dfs (1,1);
	int x = 1;
	int i = 1,en=0;
	g.push_back(0);
	while (i<=k) {
		x = go[x];
		if (vis[x]) {
			en = x;
			break;
		}
		g.push_back(x);
		vis[x] = i;
		i++;
	}
	if (i>k) {
		cout << x << "\n";
		return 0;
	}
	int b = g.size() - 1;
	vector<int> cc;
	for (int i=vis[x]; i<=b; i++) cc.push_back(g[i]);
	k -= vis[x]-1;
	k %= cc.size(); if (k == 0) k = cc.size();
	cout << cc[k-1] << '\n';
}

## GCDIST

#### Subtask 1

Làm trâu $O(n^2)$.

#### Subtask 2

Do $a_i = 1$ nên ta quy nó về bài toán tìm Diameter.

#### Subtask 3

Ta có một cận về số ước của một số: $d(u) = \sqrt[3] u \times \alpha$, với $\alpha$ là hằng số nhỏ.

Ở đây ta có thể quy ước các số trong khoảng $[1,10^5]$ có không quá $100$ ước.

Từ đây ta có thể áp dụng Small To Large hoặc xây cây mới, với đỉnh được đẩy vào theo các ước của nó.

Subtask này khá có tình edu nên các bạn có thể code thử nhé!

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
vector<int> pp[N*5];
void sieve () {
	int n = 5e5;
	for (int i=1; i<=n; i++) {
		for (int j=i; j<=n; j+=i) {
			pp[j].push_back(i);
		}
	}
}
unordered_map<int,int> mp[N];
int lv[N];
int res = 0;
int n;
struct edge {
	int v,w;
};
int a[N];
vector<edge> adj[N];
void dfs (int u, int p) {
	for (auto val : pp[a[u]]) {
		mp[u][val] = max (mp[u][val],lv[u]*val);
	}
	for (auto x : adj[u]) {
		int v = x.v, w = x.w;
		if (v == p) continue;
		lv[v] = lv[u] + w;
		dfs(v,u);
		if (mp[v].size() > mp[u].size()) swap(mp[u],mp[v]);
		for (auto it : mp[v]) {
			if (mp[u].count(it.first)) {
				res = max (res,it.second + mp[u][it.first] - 2*lv[u]*it.first);
			}
			mp[u][it.first] = max (mp[u][it.first],it.second);
		}
	}
}
void solve () {
	if (n == 0) exit(0);
	for (int i=1; i<=n; i++) {
		cin >> a[i];
		adj[i].clear();
		mp[i].clear();
	}
	for (int i=2; i<=n; i++) {
		int u,v,w; cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	} 
	res = 0;
	dfs(1,1);
	cout << res << '\n';
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	sieve();
	cin >> n; solve();
}

#### Subtask 4

Vẫn dựa vào cận $d(u)$ ở trên.

Ta có tập $S(t)$ gồm các đỉnh $u$ với $t$ là ước của $a(u)$.

Dựa vào gợi ý từ subtask $2$, dễ thấy bài toán quy về, với mỗi tập $S(t)$, tìm Diameter của tập $S(t)$. Lúc ấy ta sẽ lấy $res = max (Diamter(S(t))\times t)$ (ta không cần quan tâm $gcd$ có đúng bằng $t$ không, bởi nếu nó không phải thì sau này xét các tập là bội của $t$ ta cũng sẽ xét tới).

Để tìm Diamter, bản chất ta không cần dựng cây DFS.

Ta vẫn sẽ làm theo tư tưởng DFS, đầu tiên là từ một đỉnh $u$ bất kì, tìm đỉnh $v$ sao cho $dist(u,v)$ lớn nhất, sau đó lại tìm đỉnh $t$ sao cho $dist(v,t)$ lớn nhất. Lúc này $dist(v,t)$ chính là Diameter của tập.

Để làm bước trên, ta cần tính được $dist(u,v)$ bất kì nhanh chóng, ta có thể nghĩ tới thuật toán $LCA$. Tuy nhiên, bài này ta cần tính $LCA$ trong $O(1)$ để không bị quá thời gian.

Đây là một kĩ thuật khá mới với một số bạn, [có thể tham khảo tại đây]([https://www.geeksforgeeks.org/lca-n-ary-tree-constant-query-o1/]).

Code

#include<bits/stdc++.h>
#pragma GCC diagnostic ignored "-Wunused-parameter"
using namespace std;
const int N = 1e5+5;
vector<int> pp[N*5];
void sieve () {
	int n = 5e5;
	for (int i=1; i<=n; i++) {
		for (int j=i; j<=n; j+=i) {
			pp[j].push_back(i);
		}
	}
}
long long lv[N];
long long res = 0;
int n;
struct edge {
	int v,w;
};
int a[N];
vector<edge> adj[N];
const int Log = 18	;
int h[N];
int ti[N],cnt;
pair<int,int> rmq[3*N][Log+1];
int LOG[2*N];
int lca(int u, int v) {
	int L = ti[u], R = ti[v];
	if (L > R) swap(L, R);
	int k = LOG[R - L + 1];
	int id = min(rmq[L][k], rmq[R - (1 << k) + 1][k]).second;
	return id;
}
void build(){
	int M = log2(2 * n);
	int N = 2 * n - 1;
	for (int i=2; i<=N; i++) LOG[i] = LOG[i/2]+1;
	for (int k = 1; k <= M; k++) {
	    for (int i = 1; i + (1 << k) <= N + 1; i++) {
	        rmq[i][k] = min(rmq[i][k - 1], rmq[i + (1 << (k - 1))][k - 1]);
	    }
	}
}
void dfs (int u, int p) {
	ti[u] = ++cnt;
	h[u] = h[p] + 1;
	rmq[cnt][0] = {h[u], u};
	for (auto x : adj[u]) {
		int v = x.v, w = x.w;
		if (v == p) continue;
		lv[v] = lv[u] + w;
		dfs(v,u);
		rmq[++cnt][0] = {h[u], u};
	}
}
long long dist (int u, int v) {
	return lv[u] + lv[v] - 2*lv[lca(u,v)];
}
bool use[N*5];
vector<int> g[N*5];
bool maxi (long long &a, long long b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
} 
long long cal (int val, vector<int> &a) {
	int u = a[0];
	long long len = 0, best = u;
	for (auto v : a) {
		if (maxi(len,dist(u,v))) {
			best = v;
		}
	}
	len = 0;
	for (auto v : a) {
		len = max (len,dist(best,v));
//		cout << val << ' ' <<  best << ' ' << v << ' ' << dist(best,v) << '\n';
	}
	return len*val;
}
void solve () {
	cnt = 0;
	vector<int> Div;
	if (n == 0) exit(0);
	for (int i=1; i<=n; i++) {
		cin >> a[i];
		adj[i].clear();
		for (auto val : pp[a[i]]) {
			g[val].push_back(i);
			if (use[val]) continue;
			Div.push_back(val);
			use[val] = true;
		}
	}
	for (int i=2; i<=n; i++) {
		int u,v,w; cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	} 
	res = 0;
	dfs(1,1);
	build();
	for (auto val : Div) {
		res = max (res, cal(val,g[val]));
		g[val].clear();
		use[val] = false;
	}
	cout << res << '\n';
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	sieve();
	cin >> n; solve();
}

## KTree

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+5;
int n,k;
vector<int> adj[N];
int ti[N],to[N],cnt;
int pos[N];
int sz[N];
int lv[N];
void cal (int u, int p) {
	ti[u] = ++cnt;
	pos[cnt] = u;
	sz[u] = 1;
	for (auto v : adj[u]) {
		if (v == p) continue;
		lv[v] = lv[u] + 1;
		cal(v,u);
		sz[u] += sz[v];
	}
	to[u] = cnt;
}
int res = 0;
int Count[N];
void add (int u, int p) {
	res += k - lv[u] + 2*lv[p];
}
void dfs (int u, int p, int keep) {
	int bigchild = -1;
	for (auto v : adj[u]) {
		if (v == p) continue;
		if (bigchild == -1 || sz[bigchild] < sz[v]) bigchild = v;
	}	
	for (auto v : adj[u]) {
		if (v == p || v == bigchild) continue;
		dfs(v,u,0);
	}
	if (bigchild != -1) dfs(bigchild,u,1);
	int t = 0;
	res += Count[k + lv[u]];
	t += Count[k + lv[u]];
	Count[lv[u]]++;
	for (auto v : adj[u]) {
		if (v == p || v == bigchild) continue;
		for (int i=ti[v]; i<=to[v]; i++) {
			int x = k - lv[pos[i]] + 2*lv[u];
			if (x >= 0) res += Count[x], t += Count[x];
		}
		for (int i=ti[v]; i<=to[v]; i++) {
			Count[lv[pos[i]]]++;
		}
	}
//	cout << u << ' ' << t << " ??\n";	
	if (keep) return;
	for (int i=ti[u]; i<=to[u]; i++) {
		Count[lv[pos[i]]]--;
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
    cin >> n >> k;
    for (int i=1; i<n; i++) {
    	int u,v;
    	cin >> u >> v;
    	adj[u].push_back(v);
    	adj[v].push_back(u);
	}
	cal(1,1);
	dfs(1,1,1);
	cout << res;
}