网站首页
编程语言
数据库
系统相关
其他分享
编程问答
abc222
2024-06-22
[题解]AT_abc222_f [ABC222F] Expensive Expense
板子题,模拟赛场切了。思路线段树换根板子题。因为需要求每一个点的答案,所以定义\(dp_i\)表示以\(i\)为根的最长距离。考虑将一个点\(v\)转化为根,树的形态会发生什么变化(假设\(v\)的父亲节点是\(u\))。发现在\(v\)子树中的节点,距离都会减少\(w_{u\tov}\),其它节点