HAOI2009 毛毛虫

wjh15101051's space

卧薪尝胆，厚积薄发。

HAOI2009 毛毛虫

Date: Sat Oct 27 21:08:54 CST 2018

In Category: NoCategory

Description：

给一棵树，选一条链，问这条链和直接挂在这条链上的点的总个数最大是多少。

$1\leqslant n\leqslant 300000$

Solution：

把每个点的度数求出来减一，这个代表他的所有儿子的个数，不包括他的父亲和他自己，这样树形 $DP$ 求出来一个最长链再加二，代表根的父亲和根，这个就是答案。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 300010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

int ind[MAXN] = {0};

void add(int a,int b)

{

	++ind[a];++ind[b];

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int f[MAXN];

bool v[MAXN];

int ans = 0;

void dp(int k)

{

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp(e[i].to);

		ans = max(ans,f[k] + f[e[i].to] + ind[k]);

		f[k] = max(f[k],f[e[i].to]);

	}

	f[k] += ind[k];

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	for(int i = 1;i <= n;++i)--ind[i];

	dp(1);

	cout << ans + 2 << endl;

	return 0;

}

In tag: DP-树形DP

wjh15101051