whale.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define INF 10000000
using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int n, k;
vector<pii> edge[200005];
int sz[200005] = {};
bool deleted[200005] = {};

int vers[200005] = {};
pii prob[200005] = {};
int freq[200005] = {};

vector<pii> updates;
deque<int> delayed;

int dfs1(int u, int p) {
	sz[u] = 1;
	for(pii v : edge[u]) {
		if(v.f != p && !deleted[v.f]) {
			sz[u] += dfs1(v.f, u);
		}
	}
	return sz[u];
}

int getCentroid(int u, int p, int n) {
	for(pii v : edge[u]) {
		if(v.f != p && !deleted[v.f] && sz[v.f] > n / 2) {
			return getCentroid(v.f, u, n);
		}
	}
	return u;
}

void addFreq(int amt) {

}

int queryFreq(int u) {

}

void dfs2(int u, int p, int dist) {

	if(p != 1) delayed.push_front(dist);

	for(pii v : edge[u]) {
		if(!deleted[v.f] && v.f != p) {
			dfs2(v.f, u, dist + v.s);

			if(p != 1) {
				for(deque<int>::iterator it = delayed.begin();it != delayed.end();it++) {
					addFreq(*it);
				}
				delayed.clear();
			}
		}
	}
}

void centroidDecomp(int u) {
	int size = dfs1(u, -1);
	int centroid = getCentroid(u, -1, size);

	deleted[centroid] = true;

	dfs2(centroid, -1, 0);

	for(pii v : edge[centroid]) {
		if(!deleted[v.f])
			centroidDecomp(v.f);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	
	cin >> n >> k;

	for(int i = 0; i < n - 1;i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--;b--;
		edge[a].pb({b,c});
		edge[b].pb({a, c});
	}

	dfs1(0, -1);

}