menu zcmimi's blog

arrow_back dfs

[WC2011]最大XOR和路径 ```cpp

include<bits/stdc++.h>

int rd(

zc
2020-06-04 12:21

(以下长度定义为边权异或和)

首先钦定一条1到n的路径

容易发现可以通过环来增广路径

路径到环中间的路程要走两次,相当于没有

那么把所有环的长度插入线性基,

直接随意找一条1到n的路径,然后

zc
2020-06-02 13:14

两次dfs即可

第一次dfs:

计算出每个点的子树,包含这个点,答案最大是多少

显然S_x=v_x+\sum\limits_{y\in son_x} [S_y>0]S_y

(若x为黑

zc
2020-04-26 16:20

线段树合并的时候取\min(\text{交换前},\text{交换后}) ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC
zc
2020-03-02 02:05

首先可以dfs处理出所有路径的重要度(路径两端子树大小乘积)

然后就是树型dp处理出每个点影响的范围的重要度总和

最后取最大值就可以了

f(dis,x)表示与x距离不超过dis的所有

zc
2020-02-14 00:06

求仙人掌直径 ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __in
zc
2020-01-28 01:17

我们可以第一次修改的时候就用第一个黑点建树,可以预处理出a_i表示i到根节点路径上点编号的最小值

我们考虑接下来将一个点x变为黑点对其他点的影响:

显然x变成黑点对它的子树内的点的

zc
2020-01-18 22:40

先两次dfs找树的直径

emmmm, n \le 300 !!!

随便写好了

原来bzoj还有一道加强版,双倍经验多好

一定要在直径上取,而且距离不可以大于s,那么单调队列的思

zc
2019-12-21 19:47

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ 
zc
2019-12-21 19:47

我们设学生1的债务为x

可以根据连边来计算出其他学生债务的表达式(ax+b)

如果出现矛盾,立即输出impossible并输出

最后可以求出x,并推出所有学生的债务 ```cpp

zc
2019-12-21 19:47
1 / 2
Search
search