首页 > 分享 > 2019计蒜客信息学提高组赛前膜你赛 #5（桜の花が咲く顷に樱花盛开之时

2019计蒜客信息学提高组赛前膜你赛 #5（桜の花が咲く顷に樱花盛开之时

花匠小妙招
2025-09-17 19:58

2019" role="presentation">2019计蒜客信息学提高组赛前膜你赛 #5

不知道打这场比赛的时候我怎么崩成这个亚子……
另外，这场比赛的情景太棒了，我这就去追番（逃

如果觉得up" role="presentation">up and" role="presentation">and down" role="presentation">down讲的不太清楚的话这里还有另一种讲的思路

T2" role="presentation">T2 桜の花が咲く顷に樱花盛开之时

呐，Darling" role="presentation">Darling，现在也很努力吗。

在吃饭之前，我们散个步好吗。

嗯？这种花朵，是叫樱花吗？

呐，将来会怎样绽放呢？

嗯！它会像我的头发一样，变的美丽吗。

诶嘿嘿，好期待呢。

呐，Darling" role="presentation">Darling，到时候一起来看吧。嗯，Darling" role="presentation">Darling，我们约定好了呦。

——02" role="presentation">02

Sakura" role="presentation">Sakura 盛开了。

有一棵有 n" role="presentation">n 个节点的樱花树，边有边权。

樱花树的每个节点上都有一朵 Sakura" role="presentation">Sakura，定义节点 i" role="presentation">i 上的 Sakura" role="presentation">Sakura 的好看程度为：∑cnt(i,j)≤kdis(i,j)" role="presentation">∑cnt(i,j)≤kdis(i,j)

其中 k" role="presentation">k 是给定常数，cnt(i,j)" role="presentation">cnt(i,j) 为点 i" role="presentation">i 到点 j" role="presentation">j 的路径经过的边数，dis(i,j)" role="presentation">dis(i,j) 为点 i" role="presentation">i 到点 j" role="presentation">j 的路径经过的边权之和。

请你求出 1∼n" role="presentation">1∼n 每个节点上的 Sakura" role="presentation">Sakura 的好看程度。

输入格式
第一行，两个正整数，n" role="presentation">n 和 k" role="presentation">k。接下来 n−1" role="presentation">n−1 行描述樱花树,每行三个正整数 u,v" role="presentation">u,v 和 w" role="presentation">w，表示 u" role="presentation">u 和 v" role="presentation">v 之间连了一条权值为 w" role="presentation">w 的边。

输出格式
一行，n" role="presentation">n 个数 1∼n" role="presentation">1∼n 每个节点的 Sakura" role="presentation">Sakura 的好看程度，用空格隔开。

数据范围
对于 20%" role="presentation">20% 的数据，树是一条链,边权 ≤1000000000" role="presentation">≤1000000000

对于另外 30%30% 的数据，n≤5000,k≤10" role="presentation">n≤5000,k≤10, 边权 ≤1000000000" role="presentation">≤1000000000

对于另外 20%" role="presentation">20% 的数据，是一张菊花图

对于 100%" role="presentation">100% 的数据，n≤300000,k≤20" role="presentation">n≤300000,k≤20, 边权 ≤1000000000" role="presentation">≤1000000000

数据全部为随机生成

题解

我还专门抓了图片来嘛-w-

整理整理思路，这题求的是每条路径上的边的权值之和，套路性的转化一下思路，我们求每条边对于每个点的贡献，我太弱了说不清楚，还是画个图吧

(绘图软件崩了……只能这么画了

这是原图，比如说我们要求以1" role="presentation">1为根的深度为3" role="presentation">3的子树的贡献，那怎么考虑呢
我们先看边edge(1,2)" role="presentation">edge(1,2)，它的贡献是多少呢？
我们发现它的贡献就是它被走了多少次，而它被走的次数就是以2" role="presentation">2为根的深度为3−1" role="presentation">3−1的子树的大小，可以看到，这个以2" role="presentation">2为根的子树包括了点集2,8,9,10,11,12,13" role="presentation">2,8,9,10,11,12,13，这个集合里的每个点走到1" role="presentation">1，都要经过边edge(1,2)" role="presentation">edge(1,2)

那么我们需要知道以每个点为根的子树大小，如果我们以1" role="presentation">1为根dfs" role="presentation">dfs一次，那么其他节点会有信息损失，比如2" role="presentation">2，我们统计siz[2][k]" role="presentation">siz[2][k] ( k" role="presentation">k是树的深度 ) 会统计不到父亲上的信息，也就是siz[1][k−1]" role="presentation">siz[1][k−1]会被遗漏。
但是如果我们以每个点为根dfs" role="presentation">dfs，会T" role="presentation">T飞的。

那怎么办呢？

其实刚刚已经暗示了，既然我们以1" role="presentation">1为根dfs" role="presentation">dfs会遗漏信息，那我们把遗漏的信息加回来就好了。

具体处理方法

我们把信息有所遗漏的叫做“临时”，用siz" role="presentation">siz数组保存，比如我们上面的siz[2][k]" role="presentation">siz[2][k]就是临时的
信息全面的叫做“最终”，用sizans" role="presentation">sizans数组保存

我们在第一次dfs" role="presentation">dfs的时候可以计算出siz" role="presentation">siz数组，这个没有难度，如果真的不明白，宁可以康康代码，但是这也是一种警示，因为这个形式的dp" role="presentation">dp实在是太基础了

for( rint i = 0; i <= k; i++ ) siz[now][i] = 1;for( rint i = head[now]; i; i = a[i].nxt ){int v = a[i].to, w = a[i].val;if( v == fa ) continue ;dfsdown( v, now );for( rint j = 1; j <= k; j++ ){siz[now][j] += siz[v][j - 1];}}

然后我们要求出sizans" role="presentation">sizans数组，就需要把遗漏的信息加回来, 也就是要把父亲产生的贡献加回来。
怎么加呢，我们可以发现，如果第一次我们以1" role="presentation">1为根dfs" role="presentation">dfs的话，那1" role="presentation">1的所有子孙都会被统计到，1" role="presentation">1并不会发生信息遗漏的情况，因为它没有祖先，那我们就考虑从信息被更新为最终信息的父节点向当前节点转移(也就是用sizans[fa][i−1]" role="presentation">sizans[fa][i−1]来更新sizans[now][i]" role="presentation">sizans[now][i])。
但是这么更新的话我们会发现一些问题，那就是有些东西被多加了一次，很容易发现是siz[now][i−2]" role="presentation">siz[now][i−2]被多加了，那我们再减去它就是最终的sizans[now][i]" role="presentation">sizans[now][i]

sizans[now][0] = 1; sizans[now][1] = siz[now][1] + sizans[fa][0];for( rint i = 2; i <= k; i++ ){sizans[now][i] = ( siz[now][i] + sizans[fa][i - 1] - siz[now][i - 2] );}

现在，我们要求解了，但是此时有了一个问题，我们知道了每个点的子(父)节点的大小，可以算出每条与这个点相连的边的贡献，但是不和这个点相连，却在这棵子树里的其他边怎么办呢，没办法，只能从子节点转移
也就是说，在第一二次dfs" role="presentation">dfs的时候我们还需要再加两个数组，去维护另一组数据，而这组数据需要由siz" role="presentation">siz和sizans" role="presentation">sizans求出

现在，我们来考虑这组数据该怎么求,把这组临时数据用dpans" role="presentation">dpans保存，最终数据用dpans2" role="presentation">dpans2保存

我们发现每个点只能算出它周边和它相连的边的贡献，如果直接用sizans" role="presentation">sizans来求dpans2" role="presentation">dpans2的话，那么会有极其多的边被重复计算，造成不必要的麻烦，所以我们选择在第一次dfs" role="presentation">dfs的时候求出临时的dpans" role="presentation">dpans，它没有统计父亲的信息，所以我们再把父亲的信息加回来

第一次dfs" role="presentation">dfs完整代码

inline void dfsdown( int now, int fa ){for( rint i = 0; i <= k; i++ ) siz[now][i] = 1;for( rint i = head[now]; i; i = a[i].nxt ){int v = a[i].to, w = a[i].val;if( v == fa ) continue ;dfsdown( v, now );for( rint j = 1; j <= k; j++ ){siz[now][j] += siz[v][j - 1];dpans[now][j] += ( w * siz[v][j - 1] + dpans[v][j - 1] );}}}

可是似乎再加父亲的信息时我们遇到一些问题，父亲sizans[fa][i−1]" role="presentation">sizans[fa][i−1]连着的其他边似乎都是正确的，唯独多加了dpans[now][i−2]" role="presentation">dpans[now][i−2]的信息和加了错误的边edge(now,fa)" role="presentation">edge(now,fa)，dpans[now][i−2]" role="presentation">dpans[now][i−2]减去即可，可是那条边呢？

遇到问题，我们可以思考这个问题到底哪里有难度:
想减去edge(now,fa)" role="presentation">edge(now,fa)，我们需要知道siz[now][i−2]" role="presentation">siz[now][i−2]和这条边的边权
我们发现，这条边难以处理是因为我们不知道它的边权
那么只要在第二次dfs" role="presentation">dfs递归的时候，我们把边权也传下来即可……

inline void dfsup( int now, int fa, int length ){sizans[now][0] = 1; sizans[now][1] = siz[now][1] + sizans[fa][0];dpans2[now][0] = 0; dpans2[now][1] = length + dpans[now][1];for( rint i = 2; i <= k; i++ ){sizans[now][i] = ( siz[now][i] + sizans[fa][i - 1] - siz[now][i - 2] );dpans2[now][i] = dpans[now][i] + ( dpans2[fa][i - 1] - dpans[now][i - 2] - length * siz[now][i - 2] + length * ( sizans[fa][i - 1] - siz[now][i - 2] ) );}for( rint i = head[now]; i; i = a[i].nxt ){int v = a[i].to, w = a[i].val;if( v == fa ) continue ;dfsup( v, now, w );}}

相对上一道题而言简单许多，我一遍过了−w−" role="presentation">−w−

完整代码

#include<bits/stdc++.h>using namespace std;#define rint register int#define ll long long ll n, k, cnt;ll head[300010], sizans[300010][21], dpans[300010][21], siz[300010][21], dpans2[300010][21];struct edge{int nxt, to, val;}a[600010];inline int read( void ){int re = 0, f = 1; char ch = getchar();while( ch > '9' || ch < '0' ){if( ch == '-' ) f = -1;ch = getchar();}while( ch >= '0' && ch <= '9' ){re = re * 10 + ch - '0';ch = getchar();}return re * f;}inline void addedge( int x, int y, int z ){a[++cnt].nxt = head[x];a[cnt].to = y;a[cnt].val = z;head[x] = cnt;}inline void dfsdown( int now, int fa ){for( rint i = 0; i <= k; i++ ) siz[now][i] = 1;for( rint i = head[now]; i; i = a[i].nxt ){int v = a[i].to, w = a[i].val;if( v == fa ) continue ;dfsdown( v, now );for( rint j = 1; j <= k; j++ ){siz[now][j] += siz[v][j - 1];dpans[now][j] += ( w * siz[v][j - 1] + dpans[v][j - 1] );}}}inline void dfsup( int now, int fa, int length ){sizans[now][0] = 1; sizans[now][1] = siz[now][1] + sizans[fa][0];dpans2[now][0] = 0; dpans2[now][1] = length + dpans[now][1];for( rint i = 2; i <= k; i++ ){sizans[now][i] = ( siz[now][i] + sizans[fa][i - 1] - siz[now][i - 2] );dpans2[now][i] = dpans[now][i] + ( dpans2[fa][i - 1] - dpans[now][i - 2] - length * siz[now][i - 2] + length * ( sizans[fa][i - 1] - siz[now][i - 2] ) );}for( rint i = head[now]; i; i = a[i].nxt ){int v = a[i].to, w = a[i].val;if( v == fa ) continue ;dfsup( v, now, w );}}int main( void ){n = read(); k = read();for( rint i = 1; i <= n - 1; i++ ){int u, v, w; u = read(); v = read(); w = read();addedge( u, v, w ); addedge( v, u, w );}dfsdown( 1, 1 );for( rint i = 0; i <= k; i++ ){sizans[1][i] = siz[1][i];dpans2[1][i] = dpans[1][i];}for( rint i = head[1]; i; i = a[i].nxt ) dfsup( a[i].to, 1, a[i].val );for( rint i = 1; i <= n; i++ ){for( rint j = 0; j <= k; j++ ) cout << dpans2[i][j] << ' ';cout << endl;}return 0;}