题意

给一颗 \(n\) 个点的树，每条边权值 \(a,\ b\)，第 \(i\) 天的长度为 \(ai\ +\ b\)。
问 \(0,\ 1,\ …,\ m\ -\ 1\) 天的直径是多长。

\(1\ \leq\ n\ \leq\ 10^5,\ 1\ \leq\ m\ \leq\ 10^6\)

做法1

点分之后求出每个子树的下凸壳，合并的时候按凸壳边数启发式合并
或者边分后求出每个下凸壳直接暴力合并
时间复杂度 \(O(n\ log^2\ n\ +\ m\ log\ n)\)

做法2

多叉树转二叉树后建点分树，求出每个点分树对于重心在点分树上的父亲的距离的下凸壳
询问时求出距离 \(root\) 最远的点，在点分树上往根跑，并询问当前重心分出的所有子树中距离这个重心的最远点更新答案
时间复杂度 \(O(n\ log^2\ n\ +\ m\ log\ n)\)

写了读入输出优化的板子和树板子

代码

#include <bits/stdc++.h>

#ifdef __WIN32
#define LLFORMAT "I64"
#define Rand() ((rand() << 15) + rand())
#else
#define LLFORMAT "ll"
#define Rand() (rand())
#endif

using namespace std;

const int maxn = 1e5 + 10, lgn = 17;

template<int input_SZ, int output_SZ> struct IO {
	char s[input_SZ], t[output_SZ], *a, *b;

	IO() { fread(s, 1, input_SZ, stdin); a = s; b = t; }
	~IO() { fwrite(t, 1, b - t, stdout); }

	char nextchar(char c) {
		return *a++;
	}

	int nextint() {
		while(*a != \'-\' && (*a < \'0\' || *a > \'9\')) ++a;
		bool flag = 0; int x = 0;
		if(*a == \'-\') ++a, flag = 1;
		while(*a >= \'0\' && *a <= \'9\') x = x * 10 + *a++ - \'0\';
		if(flag) x = -x;
		return x;
	}

	long long nextll() {
		while(*a != \'-\' && (*a < \'0\' || *a > \'9\')) ++a;
		bool flag = 0; long long x = 0;
		if(*a == \'-\') ++a, flag = 1;
		while(*a >= \'0\' && *a <= \'9\') x = x * 10 + *a++ - \'0\';
		if(flag) x = -x;
		return x;
	}

	void outchar(char c) {
		*b++ = c;
		if(b - t > output_SZ - 25) { fwrite(t, 1, b - t, stdout); b = t; }
		return;
	}

	template<typename T> void outnum(T x) {
		if(!x) { *b++ = \'0\'; return; }
		if(x < 0) *b++ = \'-\', x = -x;
		static char s[20], *a;
		a = s;
		while(x) {
			T y = x / 10;
			*a++ = x - y * 10 + \'0\';
			x = y;
		}
		while(a != s) *b++ = *--a;
		if(b - t > output_SZ - 25) { fwrite(t, 1, b - t, stdout); b = t; }
		return;
	}

	template<typename T> void outnum(T x, char c) {
		return outnum(x), outchar(c);
	}
};

IO<(1 << 22) | 10, (1 << 23) | 10> io;

struct Info {
	long long a, b;

	Info() { a = b = 0; }
	Info(long long a, long long b): a(a), b(b) {};

	inline long long val(long long t) const { return a * t+ b; }
};

Info operator + (const Info &a, const Info &b) { return Info(a.a + b.a, a.b + b.b); }
Info operator - (const Info &a, const Info &b) { return Info(a.a - b.a, a.b - b.b); }

template<typename w_type, int maxn, int lgn> struct Tree {
	vector<pair<int, w_type> > g[maxn];
	vector<int> son[maxn];
	int rt, n, T, par[maxn][lgn], dep[maxn], st[maxn << 1][lgn + 1], LOG[maxn << 1], dfn[maxn], End[maxn], cent_par[maxn];
	bool vis[maxn];
	w_type dst[maxn];

	void init(int _n) { rt = 1, n = _n; T = 0; for (int u = 1; u <= n; ++u) g[u].clear(); }

	void add_biedge(int u, int v, w_type w) { g[u].push_back(make_pair(v, w)); g[v].push_back(make_pair(u, w)); return; }

	void dfs_on(int u = 1, int p = 0) {
		dep[u] = dep[par[u][0] = p] + 1;
		for (auto &e: g[u]) if(e.first != p) dst[e.first] = dst[u] + e.second, dfs_on(e.first, u);
		return;
	}

	void dfs(int u = 1, int p = 0) {
		dep[u] = dep[par[u][0] = p] + 1;
		for (int i = 1; i < lgn; ++i) par[u][i] = par[par[u][i - 1]][i - 1];
		st[dfn[u] = ++T][0] = u;
		for (auto &e: g[u]) if(e.first != p) dst[e.first] = dst[u] + e.second, dfs(e.first, u), st[++T][0] = u;
		End[u] = T;
		return;
	}

	int dep_min(int u, int v) {
		return dep[u] < dep[v] ? u : v;
	}

	void lca_init() {
		for (int i = 2; i <= T; ++i) LOG[i] = LOG[i >> 1] + 1;
		for (int lg = 1; lg <= LOG[T]; ++lg) {
			int l = 1 << lg - 1;
			for (int i = 1; i + l <= T; ++i) st[i][lg] = dep_min(st[i][lg - 1], st[i + l][lg - 1]);
		}
		return;
	}

	int lca(int u, int v) { // need dfs, lca_init
		int l = dfn[u], r = dfn[v];
		if(l > r) swap(l, r);
		int lg = LOG[r - l + 1];
		return dep_min(st[l][lg], st[r - (1 << lg) + 1][lg]);
	}

	w_type dist(int u, int v) {
		int f = lca(u, v);
		return dst[u] + dst[v] - dst[f] - dst[f];
	}

	int trans(vector<pair<pair<int, int>, w_type> > &E) { // trans to tree with degrees at most 3, E are all edges connect to children, need dfs_on, return n
		static vector<pair<int, w_type> > gg[maxn << 1];
		int _n = n;
		for (int u = 1; u <= n * 2; ++u) gg[u].clear();
		for (int u = 1; u <= n; ++u) {
			for (auto &e: g[u]) if(e.first != par[u][0]) {
				if(gg[u].size() == 2) { gg[++_n] = gg[u]; gg[u] = vector<pair<int, w_type> > { make_pair(_n, w_type()) }; }
				gg[u].push_back(e);
			}
		}
		E.clear();
		for (int u = 1; u <= _n; ++u) for (auto &e: gg[u]) E.push_back(make_pair(make_pair(u, e.first), e.second));
		return _n;
	}

	void cent_init() { memset(vis, 0, sizeof(vis[0]) * (n + 1)); for (int u = 1; u <= n; ++u) son[u].clear(); return; }

	int centroid(int u) {
		static int par[maxn], q[maxn], sz[maxn], hs[maxn], fnt, rar;
		fnt = rar = 0; par[q[rar++] = u] = 0;
		while(fnt != rar) {
			u = q[fnt++]; hs[u] = 0; sz[u] = 1;
			for (auto &e: g[u]) if(e.first != par[u] && !vis[e.first]) par[q[rar++] = e.first] = u;
		}
		for (int i = rar - 1; ~i; --i) {
			u = q[i]; hs[u] = max(hs[u], rar - sz[u]);
			if((hs[u] << 1) <= rar) return u;
			int p = par[u], x = sz[u];
			hs[p] = max(hs[p], x); sz[p] += x;
		}
	}

	int cent_dfs(int u = 1) { // build centroid decomposition tree, return centroid
		u = centroid(u);
		vis[u] = 1;
		for (auto &e: g[u]) if(!vis[e.first]) {
			int v = cent_dfs(e.first);
			son[u].push_back(v);
			cent_par[v] = u;
		}
		return u;
	}
};

int n, m;
Tree<Info, maxn << 1, lgn + 1> T;
vector<pair<pair<int, int>, Info> > E;
vector<int> sub[maxn << 1];
deque<pair<int, int> > all[maxn << 1];
Info foo[maxn << 1];

void dfs(int u) {
	sub[u] = vector<int>{u};
	for (int v: T.son[u]) {
		dfs(v);
		sub[u].insert(sub[u].end(), sub[v].begin(), sub[v].end());
		sub[v].clear();
	}
	for (int v: sub[u]) foo[v] = T.dist((T.cent_par[u] ? T.cent_par[u] : u), v);
	sort(sub[u].begin(), sub[u].end(), [&](int u, int v) { return foo[u].a < foo[v].a; });
	for (int v: sub[u]) {
		while(all[u].size() && foo[all[u].back().second].val(all[u].back().first) <= foo[v].val(all[u].back().first)) all[u].pop_back();
		if(!all[u].size()) { all[u] = deque<pair<int, int> > { make_pair(0, v) }; continue; }
		auto x = foo[all[u].back().second], y = foo[v];
		if(x.a == y.a || x.val(m - 1) >= y.val(m - 1)) continue;
		long long T = (y.b - x.b) / (x.a - y.a) - 3;
		while(x.val(T) >= y.val(T)) ++T;
		if(T < m) all[u].push_back(make_pair(T, v));
	}
	return;
}

int main() {
	n = io.nextint(); m = io.nextint();
	if(n == 1) { for (int i = 0; i < m; ++i) io.outnum(0, (i == m - 1 ? \'\n\' : \' \')); return 0; }
	T.init(n);
	for (int i = 1; i < n; ++i) {
		int u, v, a, b;
		u = io.nextint(); v = io.nextint(); a = io.nextint(); b = io.nextint();
		T.add_biedge(u, v, Info(a, b));
	}
	T.dfs_on();
	T.init(T.trans(E));
	for (auto &e: E) T.add_biedge(e.first.first, e.first.second, e.second);
	E.clear();
	T.dfs();
	T.lca_init();
	T.cent_init();
	T.rt = T.cent_dfs();
	dfs(T.rt);
	for (long long t = 0; t < m; ++t) {
		long long ans = 0;
		while(all[T.rt].size() > 1 && all[T.rt][1].first <= t) all[T.rt].pop_front();
		int u = all[T.rt][0].second;
		for (int x = T.cent_par[u]; x; x = T.cent_par[x]) {
			ans = max(ans, T.dist(u, x).val(t));
			for (int y: T.son[x]) {
				while(all[y].size() > 1 && all[y][1].first <= t) all[y].pop_front();
				ans = max(ans, T.dist(u, all[y][0].second).val(t));
			}
		}
		io.outnum(ans, (t == m - 1 ? \'\n\' : \' \'));
	}
	return 0;
}