day3下午

清北学堂--刷题班

题解

t1

并查集维护连通性，
一个联通块大于等于2，无解
有解，有一个环，没环，两种情况。
1、有一个环，章鱼图，环上的边有两个方案，总共的方案也是2
2、没有环的图，树，n个点的树，n-1条边，只有一个点没有分配到边，让他做根，所有的边都往下分配，所以有n个方案。

t2

奇数次方的位为0，
所有相同的数，化成相应的进制之后，偶数位全部为0

数位dp,

t3

贪心，

选择的节点一定是叶节点。
预处理所有的叶节点到1的和。
贪心选叶子节点最大的节点。
预处理前缀和，从根到每个叶节点价值的前缀和，暴力修改每个子树的价值。剩下的点重新算一遍，再在剩下的点中选择最大的。

选出最大的叶节点，
修改节点的值最慢，
修改一个点，会影响的子树，
dfs序上一段连续的区间，可以用线段树维护，减法。
查询，区间最大值（根节点的最大值）。

树链剖分，定义重儿子，以价值最大的儿子为重儿子，抽出所有链，排序，取前k大。

解题报告及总结

预计
>=30(30~70) +30 + 60
实际30＋30＋70

今天下午。。算错了时间。。
t1写了1个半小时，，，结果：一个小时==0

t1

半小时想了下然后打完暴力
首先没推出结论，写了一个tarjan+dfs...
算错了时间，写了1个半小时，
然后后面的都tle了。

t2

最后一个小时内，疯狂的敲完调试完，然后30。

t3

最后一个小时内，疯狂的敲完调试完，70!!!，整场考试分都在这里，时间却都放在了t1.。。。

总结：
今天的一天都不是很好，上午的题第二题没有读完题。。。下午算错了时间，。。。
以后还要注意，