zcmimi's blog

arrow_back虚树共6篇文章

avatar
zcmimi
2020-09-25 14:51:21

虚树是一种统计树上信息的技术

例题: LG 2495 [SDOI2011]消耗战

如果树的点数很少,可以直接树上dp

可以发现\sum k_i \le 5 \times 10^5

我们可以每次都把提供

avatar
zc
2020-02-01 00:38:00
查看原题

点击跳转

可以发现按dfs序排序后路径是a_1,a_2,a_3,...,a_k,a_1

那答案就是dist(a_1,a_2)+dist(a_2,a_3)+...+dist(a_k,a_1)

设现在要插入x,y,zx的前驱后继(dfs序上)

那么ans+=dist(y,x)+dist(x,z),ans-=dist(y,z)

删去x同理

avatar
zc
2020-01-30 09:40:00
查看原题

点击跳转

先来考虑普通的树型dp怎么做

SZ_x表示x的子树中有多少个查询点,d_x表示x的深度

  1. 这些新通道的代价和

    考虑每条边要被统计多少次:

    假设yx的某个子节点,x\leftrightarrow y会被统计(k-SZ_y)\times SZ_y次,

    (起点可以是y的子树中任一查询点,终点可以是y子树外的任一查询点,这样的话路径必然经过x\leftrightarrow y)

    那么贡献是(d_y-d_x)\times (k-SZ_y)\times SZ_y

  2. 这些新通道中代价最小/大的是多少

    有点类似树型dp求树的直径

    x的子树中最长的路径是: 子树中深度最大的查询点的深度+子树中深度次大的查询点的深度(若x是查询点则包括x\leftrightarrow x,深度为0)

    最短路径和上面的求法类似

套上虚树就可以解决这道题了

如果不懂的话就看代码咯

avatar
zc
2020-01-29 15:02:00
查看原题

点击跳转

avatar
zc
2020-01-29 08:06:00
查看原题

点击跳转

avatar
zc
2020-01-28 21:26:00
查看原题

点击跳转

1/1
Search
search