Description
A tree with N nodes and N-1 edges is given. To connect or disconnect one edge, we need 1 unit of cost respectively. The nodes are labeled from 1 to N. Your job is to transform the tree to a cycle(without superfluous edges) using minimal cost.
A cycle of n nodes is defined as follows: (1)a graph with n nodes and n edges (2)the degree of every node is 2 (3) each node can reach every other node with these N edges.
A cycle of n nodes is defined as follows: (1)a graph with n nodes and n edges (2)the degree of every node is 2 (3) each node can reach every other node with these N edges.
Input
The first line contains the number of test cases T( T<=10 ). Following lines are the scenarios of each test case. In the first line of each test case, there is a single integer N( 3<=N<=1000000 ) - the number of nodes in the tree. The following N-1 lines describe the N-1 edges of the tree. Each line has a pair of integer U, V ( 1<=U,V<=N ), describing a bidirectional edge (U, V).
Output
For each test case, please output one integer representing minimal cost to transform the tree to a cycle.
题目大意:一棵有n个点的树,删边需要1的费用,增边需要1的费用,问最少需要多少费用才能得到一个环,不能用多余的边(即总共n条边)。
思路:首先我们可以这样考虑:我们先删掉x条边,那么之后再加上x+1条边,形成一个环。我们删掉x条边后,所有的点的度都不能大于2,那么就会出现多条链,再用x+1条边把这些链首尾相接就可以形成一个环。现在问题就转化成了给一棵树,问最少删掉多少条边,使得每个点的度不大于2。然后就是树状DP,用dp[i][0]表示,第i个点,连0个或1个子节点(度小于2)的最小费用。用dp[i][1]表示,第i个点,连0个或1个或2个子节点(度小于等于2)的最小费用。这样对每个点选择是不连或者连一个子节点,还是连两个子节点。然后随便搞,时间复杂度为O(n)。
PS:100W个点我看到好多人栈溢出了所以大家还是写非递归吧(实际上会不会溢出我不知道我没试过我一开始就写非递归)……我极少写非递归可能写得比较挫……
代码(2703MS):
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 using namespace std; 6 7 const int MAXN = 1000010; 8 const int MAXE = MAXN * 2; 9 10 int head[MAXN]; 11 int stk[MAXN], stkp[MAXN], top; 12 int next[MAXE], to[MAXE]; 13 int ecnt, n, T; 14 15 void init() { 16 memset(head, 0, sizeof(head)); 17 ecnt = 1; 18 } 19 20 void add_edge(int u, int v) { 21 to[ecnt] = v; next[ecnt] = head[u]; head[u] = ecnt++; 22 to[ecnt] = u; next[ecnt] = head[v]; head[v] = ecnt++; 23 } 24 25 int dp[MAXN][2]; 26 //0:连0 or 1个子节点,1:连两个子节点 27 int solve() { 28 top = 1; 29 stk[top] = 1; stkp[top] = head[1]; 30 while(top > 0) { 31 int &p = stkp[top], u = stk[top]; 32 if(to[p] == stk[top - 1]) p = next[p]; 33 if(p) { 34 int &v = to[p]; 35 ++top; stk[top] = v; stkp[top] = head[v]; 36 p = next[p]; 37 } 38 else { 39 int min1 = MAXN, min2 = MAXN; 40 dp[u][0] = 0; 41 for(int q = head[u]; q; q = next[q]) { 42 int &v = to[q]; 43 if(v == stk[top - 1]) continue; 44 ++dp[u][0]; 45 dp[u][0] += min(dp[v][0], dp[v][1]); 46 int x = dp[v][0] - min(dp[v][0], dp[v][1]); 47 if(x < min1) { 48 min2 = min1; 49 min1 = x; 50 } 51 else min2 = min(min2, x); 52 } 53 int best = dp[u][0]; 54 dp[u][0] = min(dp[u][0], best - 1 + min1); 55 dp[u][1] = min(dp[u][0], best - 2 + min1 + min2); 56 --top; 57 } 58 } 59 return 2 * min(dp[1][0], dp[1][1]) + 1; 60 } 61 62 int main() { 63 scanf("%d", &T); 64 while(T--) { 65 scanf("%d", &n); 66 init(); 67 int u, v; 68 for(int i = 1; i < n; ++i) { 69 scanf("%d%d", &u, &v); 70 add_edge(u, v); 71 } 72 printf("%d ", solve()); 73 } 74 }