font return mil sca str clas 删掉 种类 ios
分析:比较神奇的一道题.要把树变成环肯定要先变成链,然后把链给拼接成环.接下来考虑一个脑洞大开的树形dp:设f[i][0]表示i不与父节点相连的链数,f[i][1]表示i与父节点相连的链数,先考虑怎么转移f[i][0],如果i不与父节点相连,那么i肯定与两个子节点相连,其它的子节点都不与父节点相连,而且要剪掉与父亲节点的一条边,所以f[i][0] = (Σf[j][0]) - f[p][0] - f[q][0] + f[p][1] + f[q][1] - 1.f[i][1]也能很容易推导出来f[i][1] = (Σf[j][0]) - f[p][0] + f[p][1].这两个式子中的p,q使我们选出来与i组成链的子节点,为了使得f[i][0/1]最小,我们要选出使f[j][1] - f[j][0]最小的p,q,这个在枚举的时候扫一下就可以了.
最后是合并,一个树有N-1条边,先不断地删边,然后加边,加到N-1条边,最后再补一条边形成一个环,可以发现删边和加边是对称的,需要删掉链-1条边,那么也需要加上链-1条边,最后用一条边形成一个环就可以了.
树形dp,考虑好链的种类和怎么从子节点转移,充分利用好加边和删边的对称性,就能A掉此题,最关键的还是状态的表示,树形dp可能会需要保存不同的状态,如果对于当前状态推不下去了,就多加点状态,直到可做为止.
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- const int inf = 0x7fffffff;
- int n, head[100010], to[200010], nextt[200010], tot = 1, f[100010][2];
- void add(int x, int y)
- {
- to[tot] = y;
- nextt[tot] = head[x];
- head[x] = tot++;
- }
- void dfs(int u, int from)
- {
- int min1 = inf, min2 = inf,son = 0,sum = 0,sum2 = 0;
- for (int i = head[u]; i; i = nextt[i])
- {
- int v = to[i];
- if (v != from)
- {
- dfs(v, u);
- son++;
- sum += f[v][0];
- sum2 += f[v][1];
- int temp = f[v][1] - f[v][0];
- if (temp < min1)
- {
- min2 = min1;
- min1 = temp;
- }
- else
- if (temp < min2)
- min2 = temp;
- }
- }
- if (son == 0)
- f[u][0] = f[u][1] = 1;
- if (son == 1)
- f[u][0] = f[u][1] = sum2;
- else
- if (son >= 2)
- {
- f[u][0] = sum + min1 + min2 - 1;
- f[u][1] = sum + min1;
- }
- }
- int main()
- {
- scanf("%d", &n);
- for (int i = 1; i < n; i++)
- {
- int u, v;
- scanf("%d%d", &u, &v);
- add(u, v);
- add(v, u);
- }
- dfs(1, 0);
- printf("%d\n", f[1][0] * 2 - 1);
- return 0;
- }
清北学堂模拟赛d3t6 c
来源: http://www.bubuko.com/infodetail-2338234.html