Submission #849404

#	Time	Username	Problem	Language	Result	Execution time	Memory
849404		luanmenglei	Paths (RMI21_paths)	C++17	100 / 100	183 ms	23888 KiB

Main

#include <bits/stdc++.h>
using namespace std;

void debug(const char *msg, ...) {
#ifdef CLESIP
    va_list arg;
    static char pbString[512];
    va_start(arg,msg);
    vsprintf(pbString,msg,arg);
    cerr << "[DEBUG] " << pbString << "\n";
    va_end(arg);
#endif    
}

using i64 = long long;
using Node = pair<i64, int>;
const int N = 1e5 + 10;
vector<pair<int, int>> G[N];
int n, k, top[N], from[N];
i64 sum[N], val[N], res, ans[N];
bool v[N];
Node son[N], seson[N], oson[N];
set<Node> s, os;

Node reduce(const Node &x, i64 k) { return { x.first - k, x.second }; }

void dfs1(int x, int fa) {
	if (G[x].size() == 1) son[x] = { sum[x], x };
	for (auto [y, z] : G[x]) if (y != fa) {
		sum[y] = sum[x] + z;
		dfs1(y, x);
		if (son[x] < son[y]) from[x] = y, seson[x] = son[x], son[x] = son[y];		
		else if (seson[x] < son[y]) seson[x] = son[y];
	}
}

void dfs2(int x, int fa) {
	for (auto [y, z] : G[x]) if (y != fa) {
		top[son[y].second] = x;
		if (from[x] == y) {
			oson[y] = max(oson[x], reduce(seson[x], sum[x]));
		} else {
			oson[y] = max(oson[x], reduce(son[x], sum[x]));
		}
		oson[y].first += z;
		dfs2(y, x);
	}
	if (son[x].second) top[son[x].second] = fa;
} 

void update(int x, i64 d) {
	if (v[x]) {
		auto it = s.find({ val[x], x });
		s.erase(it), res -= val[x];
		val[x] += d;
		if (!os.empty() && prev(os.end()) -> first > val[x]) {
			it = prev(os.end());
			s.insert(*it), res += it -> first, v[it -> second] = true;
			os.erase(it);
			os.emplace(val[x], x), v[x] = false;
		} else {
			s.emplace(val[x], x), res += val[x];
		}
	} else {
		auto it = os.find({ val[x], x });
		os.erase(it);
		val[x] += d;
		if ((int) s.size() < k || s.begin()->first < val[x]) {
			it = s.begin();
			res -= it -> first, v[it -> second] = false, os.insert(*it);
			s.erase(it);
			s.emplace(val[x], x), res += val[x], v[x] = true;
		} else {
			os.emplace(val[x], x);
		}
	}
}

void dfs3(int x, int fa) {
	ans[x] = res;
	for (auto [y, z] : G[x]) if (y != fa) {
		update(son[y].second, -z);
		update(oson[y].second, z);
		dfs3(y, x);
		update(son[y].second, z);
		update(oson[y].second, -z);
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for (int i = 1, x, y, z; i < n; i ++) {
		cin >> x >> y >> z;
		G[x].emplace_back(y, z);
		G[y].emplace_back(x, z);
	}
	dfs1(1, 0), dfs2(1, 0);
	for (int i = 1; i <= n; i ++) if (G[i].size() == 1) {
		val[i] = sum[i] - sum[top[i]];
		s.emplace(val[i], i);
		v[i] = true, res += val[i];
		if ((int) s.size() > k) {
			auto it = s.begin();
			v[it -> second] = false, res -= it -> first;
			os.insert(*it), s.erase(it);
		}
	}
	dfs3(1, 0);
	for (int i = 1; i <= n; i ++) cout << ans[i] << "\n";
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32