zcmimi's blog

arrow_backset共6篇文章

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
2019-12-21 19:47:00
查看原题

点击跳转

在每条重链上搞一个set

或者用线段树+二分

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先用set预处理出离每个点最近的点和第二近的点

n~1 每次往set里插入{a[i],i} 然后把前驱后继找出来比较一下 具体看代码

(听说有排序后双向链表的神仙做法)

接着用倍增处理出开2^i循环次的数据

然后就直接暴力

具体看代码,码风有点新奇

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

  1. b_i = a_i + 1

    一条链

    直接二分最小值,然后判断即可

  2. m=1

    直接找树的直径

  3. a_i = 1

    记录所有边权,设边权为w,然后排序

    w_1 + w_{2m} , w_2 + w_{2m-1}, ...的最小值

  4. 分支不超过3(基本上就是正解了)

明摆着就是正解嘛

dfs(x,f,w)求出x的子树连接x长度不超过w的最长路径

路径分为两种

一种\ge w,那直接条数++

另一种a+b \ge w

那我们直接用multiset存,每次lowerbound找到最接近的,然后返回

stl,还是太弱了Q\omega Q

1/1
Search
search