plus-TreeDP

代码在这里My code

A题

题意：给一棵树，求最长链上LIS。
类似序列求LIS的O(nlogn)做法，对每个点i维护一个向下长度为j的上升序列的最小末端值，下降序列的最大末端值。更新答案的时候用前缀和&后缀和优化一下就可以了……写起来有点麻烦

C题

题意：给一棵树，树上每条边都已经定向，现求反向最少的边数，使得可以从两个点顺着边控制树上的全部节点。
枚举分割点，O(n^2)计算即可。

F题

题意：每个点有一堆电池，每次吃一个电池然后走一步，问最多可以吃多少个电池？
考虑一个贪心：我能向儿子走的话是一定要向儿子走的，但是一定要留下一个走回我的父亲，如果不能将所有儿子的都拿走的话，就选最大的那几个，然后如果还有剩下的，就可以将儿子点上剩下的拿走一些（两个点之间来回走）。

I题

题意：给一棵仙人掌，问从x走到y，不同的走法有多少种，只要经过的边集不同即算不同。
缩一下点，看经过了多少个环即可（ans=2^num)
考虑另一个问题：如果是要求点集不同呢？
则可以给每个环新建一个特殊点，连向所有环上的点，再将原图环内连边去掉，这样就将原图重构成了一棵树，最后只需要看经过了多少个特殊点就可以了

K题

题意：给一棵树，加一条边后，x，y这两点在环上的情况下，环的长度的期望值。
对于一个点dp一下子树到根的距离和，以及除子树外所有点到x的距离和，乘一乘= =
我WA的原因：$\sum_{i}\sum_{j} (i + j)$算成了 $(\sum_{i} i + \sum_{j} j)$

• ← Previous Post