题目
题解
这里给出一个不依赖子树标号连续的做法。
我们可以认为，如果一条路径上还有一条边的边权没有固定，那么这条路径的权是容易计算的。
我们可以认为，一开始所有点都是独立的，每次添加一条边。当一条路径的两个点连通时，这条路径上的边权就全部固定了。
我们需要做的是合并两个连通块，启发式合并即可。
代码
/* C++20 is required!
* By rbtree (https://rbtr.ee)
* Email n@rbtr.ee
* もしも生まれ変われるなら 同じ路を歩みたいと
__ __ __ _
_____/ /_ / /_________ ___ / /______ (_)______ __
/ ___/ __ \/ __/ ___/ _ \/ _ \ ______ / //_/ __ \/ / ___/ / / /
/ / / /_/ / /_/ / / __/ __/ /_____/ / ,< / /_/ / / /__/ /_/ /
/_/ /_.___/\__/_/ \___/\___/ /_/|_|\____/_/\___/\__, /
SIGN /___*/
#include <bits/stdc++.h>
#define __NO_MAIN__ false
constexpr bool MTS = true, SPC_MTS = false;
#define FULL(arg) arg.begin(), arg.end()
// :/
using namespace std;
using tp = long long int;
using vetp = basic_string<tp>;
[[maybe_unused]] constexpr tp ZERO = 0, ONE = 1, INF = -1ull >> 2;
int WITHERING(unsigned long long int);
void MIST();
#if !__NO_MAIN__
int main(int argc,char* argv[]){unsigned long long int t=0,_t=1;if(MTS&&!SPC_MTS
) cin >>_t;MIST();while(t<_t||SPC_MTS){if(WITHERING(++t)!=0)return 0;}return 0;}
#endif
template <typename _Ty> class _Lambda_t {_Ty lexp;public:template<typename __Ty>
_Lambda_t(__Ty&&lexp):lexp(static_cast<__Ty&&>(lexp)){}template<typename... __Ty
>decltype(auto)operator()(__Ty&&...args){return lexp(std::ref(*this),static_cast
<__Ty&&>(args)...); } }; template <typename _Ty> decltype(auto) lexp(_Ty&&l_exp)
{ return _Lambda_t<typename std::decay<_Ty>::type>(static_cast<_Ty&&>(l_exp)); }
template <typename _Ty1, typename _Ty2> bool cmax(_Ty1& a, const _Ty2& b) { if (
a<b){a=b; return true; } return false; } template <typename _Ty1, typename _Ty2>
bool cmin(_Ty1&a,const _Ty2&b){if(b < a) { a = b; return true; } return false; }
#ifdef XCODE
#define bg(...){cout<<"["<<__LINE__<<'@'<<++_LT[__LINE__]<<':';BG(__VA_ARGS__);}
size_t _LT[21777]; template<typename _Type>void BG(const _Type&_cur){cout<<' '<<
_cur << ']' <<" <<:"<<std::endl;}template<typename _Type,typename... _Other>void
BG(const _Type& _cur, const _Other& ..._other) {cout<< ' '<<_cur;BG(_other...);}
#else
#define bg(...)
#define dputs(...)
#endif
// :/
namespace lib { // LIBLIBLIBLIBLIBLIBLIBLIBLIBLIBLIBLIBLIBLIBLIBLIBLIBLIBLIBLIB
using _Ty = size_t; struct DSU {vector<_Ty> f,s;vector<pair<_Ty,_Ty>>g,h;DSU(_Ty
t) { f.resize(t); s=vector<_Ty>(t,1);iota(f.begin(),f.end(),0);}_Ty root(_Ty x){
return f[x]==x?x:root(f[x]);}void link(_Ty u,_Ty v){u=root(u);v=root(v);if(s[u]>
s[v]) swap(u,v);g.emplace_back(v,s[v]);h.emplace_back(u,f[u]);if(u==v)return;f[u
]=v;s[v]+=s[u];}_Ty size(_Ty x){return s[root(x)];}void undo(){f[h.back().first]
=h.back().second;s[g.back().first]=g.back().second;g.pop_back();h.pop_back();}};
} // LIB::DSU LIB::DSU LIB::DSU LIB::DSU LIB::DSU LIB::DSU LIB::DSU LIB::DSU LI
// :/
struct STRUGGLE {
STRUGGLE() {
cin.tie(nullptr)->sync_with_stdio(false);
}
} STRUGGLE;
void MIST() {
}
int WITHERING([[maybe_unused]] unsigned long long int TEST_NUMBER) {
tp n, W, r = 1; cin >> n >> W;
vector<tp> t(n * 4 + 1, 0);
auto g = t;
vector<tp> dep(n + 1), f(n + 1), hson(n + 1), s(n + 1), top(n + 1), dfn(n + 1), real(n + 1);
vector<vector<tp>> e(n + 1);
for (tp i = 2; i <= n; ++i) {
tp u = i, v; cin >> v;
e[u].push_back(v);
e[v].push_back(u);
}
auto dfs1 = [&](auto& _, tp x) -> void {
dep[x] = dep[f[x]] + 1;
s[x] = 1;
for (auto& i : e[x]) {
if (i == f[x]) continue;
f[i] = x;
_(_, i);
s[x] += s[i];
if (s[i] > s[hson[x]]) hson[x] = i;
}
};
tp cnt = 0;
auto dfs2 = [&](auto& _, tp x, tp h) -> void {
real[dfn[x] = ++cnt] = x;
top[x] = h;
if (!hson[x]) return;
_(_, hson[x], h);
for (auto& i : e[x]) {
if (i != f[x] && i != hson[x]) _(_, i, i);
}
};
auto modify = [&](auto& _, tp x, tp l, tp r, tp ml, tp mr, tp k) -> tp {
if (ml <= l && r <= mr) {
g[x] += k;
return k * (r - l + 1);
} else {
tp mid = (l + r) / 2, ret = 0;
if (mid >= ml) ret += _(_, x * 2, l, mid, ml, mr, k);
if (mid < mr) ret += _(_, x * 2 + 1, mid + 1, r, ml, mr, k);
t[x] += ret;
return ret;
}
};
auto query = [&](auto& _, tp x, tp l, tp r, tp ml, tp mr, tp acc = 0) -> tp {
acc += g[x];
if (ml <= l && r <= mr) return (acc * (r - l + 1) + t[x]);
else {
tp mid = (l + r) / 2, ret = 0;
if (mid >= ml) ret += _(_, x * 2, l, mid, ml, mr, acc);
if (mid < mr) ret += _(_, x * 2 + 1, mid + 1, r, ml, mr, acc);
return ret;
}
};
auto LCA = [&](tp x, tp y) {
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) x = f[top[x]];
else y = f[top[y]];
}
return dep[x] < dep[y] ? x : y;
};
auto add = [&](tp x, tp y, tp z) -> void {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
modify(modify, 1, 1, n, dfn[top[x]], dfn[x], z);
x = f[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
modify(modify, 1, 1, n, dfn[x], dfn[y], z);
};
auto qry = [&](tp x, tp y) -> tp {
tp acc = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
acc += query(query, 1, 1, n, dfn[top[x]], dfn[x]);
x = f[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
return acc + query(query, 1, 1, n, dfn[x], dfn[y]);
};
dfs1(dfs1, r);
dfs2(dfs2, r, r);
for (tp i = 1; i <= n; ++i) {
tp j = i % n + 1;
tp lca = LCA(i, j);
add(i, lca, 1);
add(j, lca, 1);
add(lca, lca, -2);
}
tp sum = n;
tp tar = 0;
vector<set<tp>> b(n + 1);
for (tp i = 1; i <= n; ++i) b[i].insert(i);
lib::DSU like(n + 1);
for (tp i = 2; i <= n; ++i) {
tp x, p; cin >> x >> p;
W -= p;
tp u = like.root(x), v = like.root(f[x]);
if (like.size(u) > like.size(v)) swap(u, v);
auto rm = [&](tp i, tp j) {
if (b[v].count(j)) --sum;
};
for (auto& i : b[u]) {
rm(i, i % n + 1);
rm(i, i == 1 ? n : i - 1);
}
tar += p * qry(x, x);
for (auto& i : b[u]) b[v].insert(i);
b[u].clear();
like.link(u, v);
cout << sum * W + tar << ' ';
}
cout << '\n';
return 0;
}
// :\ */