深圳哪里有做网站的公司,优惠券网站建设制作,2012年网站设计方法,金湖网站设计题目描述 经过了几周的辛苦工作,贝茜终于迎来了一个假期.作为奶牛群中最会社交的牛,她希望去拜访N(1N50000)个朋友.这些朋友被标号为1..N.这些奶牛有一个不同寻常的交通系统,里面有N-1条路,每条路连接了一对编号为C1和C2的奶牛(1 C1 N; 1 C2 N; C1…题目描述 经过了几周的辛苦工作,贝茜终于迎来了一个假期.作为奶牛群中最会社交的牛,她希望去拜访N(1N50000)个朋友.这些朋友被标号为1..N.这些奶牛有一个不同寻常的交通系统,里面有N-1条路,每条路连接了一对编号为C1和C2的奶牛(1 C1 N; 1 C2 N; C1C2).这样,在每一对奶牛之间都有一条唯一的通路.FJ希望贝茜尽快的回到农场.于是,他就指示贝茜,如果对于一条路直接相连的两个奶牛,贝茜只能拜访其中的一个.当然,贝茜希望她的假期越长越好,所以她想知道她可以拜访的奶牛的最大数目. 输入 第1行:单独的一个整数N第2..N行:每一行两个整数,代表了一条路的C1和C2. 输出 单独的一个整数,代表了贝茜可以拜访的奶牛的最大数目. 样例输入 76 23 42 31 27 65 6 样例输出 4 分析 树上DP。 dp[i][0]表示不选i以i为根的子树的最大答案。 dp[i][1]表示选i以i为根的子树的最大答案。 状态转移方程dp[i][0]∑max(dp[j][0],dp[j][1])dp[i][1]1∑f[dp][0] #include iostream
#include string
#include cstdio
#include cmath
#include cstring
#include algorithm
#include vector
#include queue
#include deque
#include map
#define range(i,a,b) for(int ia;ib;i)
#define LL long long
#define rerange(i,a,b) for(int ia;ib;--i)
#define fill(arr,tmp) memset(arr,tmp,sizeof(arr))
using namespace std;
pairint,inte[150005];
int tol,h[50005],dp[50005][2],n;
void add_edge(int x,int y){e[tol].firsty;e[tol].secondh[x];h[x]tol;
}
void init() {cinn;range(i,1,n-1){int x,y;cinxy;add_edge(x,y);add_edge(y,x);}
}
void dfs(int x,int fu){dp[x][1]1,dp[x][0]0;for(int ih[x];i;ie[i].second){int fire[i].first;if(firfu)continue;dfs(fir,x);dp[x][1]dp[fir][0];dp[x][0]max(dp[fir][1],dp[fir][0]);}
}
void solve(){dfs(1,0);coutmax(dp[1][0],dp[1][1])endl;
}
int main() {init();solve();return 0;
} View Code 转载于:https://www.cnblogs.com/Rhythm-/p/9333673.html
