烟台制作网站,什么是域名,旅游类网站策划建设_,wordpress搜索ajax题目是问把一棵树通过剪边、加边形成一个环的最小代价。 分成两步#xff0c;先把树剪成一些链#xff0c;再把链连接成一个环。 设一棵有n个节点的树#xff0c;剪掉X条边后#xff0c;形成L条链。 那么代价为XL。 n-1-XedgeNum(L条链) ① //原本有n-1条边#xff0c;剪掉… 题目是问把一棵树通过剪边、加边形成一个环的最小代价。 分成两步先把树剪成一些链再把链连接成一个环。 设一棵有n个节点的树剪掉X条边后形成L条链。 那么代价为XL。 n-1-XedgeNum(L条链) ① //原本有n-1条边剪掉X条还剩edgeNum(L条链)条 edgeNum(L条链)Ln ② //L条链的这些边L条边形成一个有n条边的环 由①、②得到LX1 则代价为 XL2*L-12*X1。 问题转化成了把一棵树剪成一些链最少能剪成几条链或者最少需要剪掉多少条边? 我觉得到了这一步问题就好解决了我是树形dp搞的求的是最少能剪成几条链。 dp[u][0]表示u节点是所在链的端点时以u节点为根节点的子树形成的最少的链数。 dp[u][1]表示u节点是所在链的中间的点时以u节点为根节点的子树形成的最少的链数。 然后就可以转移了。 1 #includecstdio2 #includecstring3 #includevector4 #pragma comment(linker, /STACK:102400000,102400000)5 using namespace std;6 const int N 1000005;7 const int inf N;8 9 vectorint G[N];
10 int dp[N][2];
11
12 inline int min(int a,int b) {return ab?a:b;}
13
14 void dfs(int u,int fa)
15 {
16 int sz G[u].size();
17 int v,cld0,sum0,min1inf,min2inf,temp;
18 for(int i0;isz;i)
19 {
20 v G[u][i];
21 if( v!fa )
22 {
23 cld;
24 dfs(v,u);
25 temp min(dp[v][0],dp[v][1]);
26 sum temp;
27 temp dp[v][0] - temp;
28 if( tempmin1 ) {min2min1;min1temp;}
29 else if( tempmin2 ) min2temp;
30 }
31 }
32 if( !cld ) dp[u][0]1,dp[u][1]inf;
33 else if( 1cld ) dp[u][0]summin1,dp[u][1]inf;
34 else
35 {
36 dp[u][0] sum min1;
37 dp[u][1] sum min1 min2 - 1;
38 }
39 }
40
41 int main()
42 {
43 int T;
44 int n,u,v;
45
46 //freopen(4714.in,r,stdin);
47 //freopen(myout.txt,w,stdout);
48 scanf(%d,T);
49 while( T-- )
50 {
51 scanf(%d,n);
52 for(int i1;in;i) G[i].clear();
53 for(int i0;in-1;i)
54 {
55 scanf(%d%d,u,v);
56 G[u].push_back(v);
57 G[v].push_back(u);
58 }
59 dfs(1,0);
60 printf(%d\n,2*min(dp[1][0],dp[1][1])-1);
61 }
62 return 0;
63 } View Code 转载于:https://www.cnblogs.com/kiwi-bird/p/3310970.html
