不会交互题格式

#include <bits/stdc++.h>

#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)
#define ep(i, u, v, w) for (int i = H[u], v = e[i].v, w = e[i].w; i; i = e[i].n, v = e[i].v, w = e[i].w)

const int _ = 2e5 + 7;
typedef long long ll;
typedef std::pair<ll, ll> PLL;
const ll inf = 4e18;

struct edge { int v, n, w; }e[_ << 1]; int H[_], cnte = 1;
int n, pr[_], dep[_], dfn[_], idx, fa[_], st[_][21], lg[_], id[_]; 
ll a[_], b[_], len[_], dp[_];
int sz[_], tmp[_], rt; bool vis[_];
std::vector <int> stk[_];
std::vector <ll> ans;

void Add(int u, int v, int w) { e[++cnte] = { v, H[u], w }, H[u] = cnte; }
void getrt(int u, int f, int total) {
	sz[u] = 1, tmp[u] = 0;
	ep(i, u, v, w) if (!vis[v] and v != f)
		getrt(v, u, total), sz[u] += sz[v], tmp[u] = std::max(tmp[u], sz[v]);
	tmp[u] = std::max(tmp[u], total - sz[u]);
	if (!rt or tmp[u] < tmp[rt]) rt = u;
}
int solve(int u, int total) {
	rt = 0, getrt(u, 0, total), vis[rt] = true; int t = rt;
	ep(i, t, v, w) if (!vis[v]) pr[solve(v, total - tmp[v])] = t;
	return t;
}
void init(int u, int f, ll d) {
	len[u] = d, dep[u] = dep[fa[u] = f] + 1, dfn[u] = ++idx, st[idx][0] = u;
	ep(i, u, v, w) if (v != f) init(v, u, d + w);
}
int upd(int x, int y) { return dep[x] < dep[y] ? x : y; }
void Init() {
	init(1, 0, 0), solve(1, n);
	lep(j, 1, 20) lep(i, 1, n - (1 << j) + 1)
		st[i][j] = upd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
	lep(i, 2, n) lg[i] = lg[i >> 1] + 1;
}
int lca(int x, int y) {
	if (dfn[x] > dfn[y]) std::swap(x, y);
	int k = lg[dfn[y] - dfn[x] + 1], p = upd(st[dfn[x]][k], st[dfn[y] - (1 << k) + 1][k]);
	return p == x ? x : fa[p];
}
ll Dis(int x, int y) { return len[x] - 2 * len[lca(x, y)] + len[y]; }
#define sz stk[x].size()
ll X(int u) { return -b[u]; }
ll Y(int x, int u) { return dp[u] + a[u] + b[u] * Dis(x, u); }
PLL mv(int x, int y, int p) { return { X(y) - X(x), Y(p, y) - Y(p, x) }; }
ll xr(PLL x, PLL y) { return x.first * y.second - x.second * y.first; }
bool ck(int x, int y, ll k, int p) { return xr({1, k}, mv(x, y, p)) >= 0; }
ll Calc(int x, int u) {
	if (sz == 0) return inf;
	int l = 0, r = sz - 1; ll k = Dis(x, u);
	while (l < r) {
		int md = (l + r) >> 1;
		if (ck(stk[x][md], stk[x][md + 1], k, x)) r = md;
		else l = md + 1;
	}
	return -X(stk[x][l]) * k + Y(x, stk[x][l]);
}
bool chk(int x, int y, int p) { if (X(x) == X(y) and Y(p, y) >= Y(p, x)) return true; return false; }
void Ins(int x, int u) {
	if (dp[u] == inf) return;
	if (sz and chk(stk[x].back(), u, x)) return;
	while (sz > 1 and xr(mv(stk[x][sz - 2], stk[x][sz - 1], x), mv(stk[x][sz - 1], u, x)) <= 0) stk[x].pop_back();
	stk[x].push_back(u);
}
#undef sz

std::vector<long long> travel(std::vector<long long> A, std::vector<int> B, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = A.size(); int u, v, w;
	lep(i, 1, n) a[i] = A[i - 1], id[i] = i;
	lep(i, 1, n) b[i] = B[i - 1], dp[i] = inf;
	dp[1] = 0;
	lep(i, 0, n - 2) u = U[i], v = V[i], w = W[i],
		++u, ++v, Add(u, v, w), Add(v, u, w);
	Init();
	std::sort(id + 1, id + 1 + n, [](const int&x, const int&y) { return b[x] > b[y]; });
	lep(j, 1, n) { int u = id[j], x = u;
		while (x) dp[u] = std::min(dp[u], Calc(x, u)), x = pr[x];
		x = u;
		while (x) Ins(x, u), x = pr[x];
	}
	lep(j, 1, n) { int u = id[j], x = u;
		while (x) dp[u] = std::min(dp[u], Calc(x, u)), x = pr[x];
	}

	lep(i, 2, n) ans.push_back(dp[i]);
	return ans;
}