Codeforces Gym 100096A Athletic competition 树型DP

admin管理员组

文章数量:1530018

http://codeforces/gym/100096/attachments

Problem A. Athletic competition

Input file: athletic.in

Output file: athletic.out

Elections are coming and the mayor of Bytetown decided to organize an athletic competition to increasehis odds. Unfortunately there is no athletic stadium in Bytetown, so all parts of the competition willhave to be held in the town’s streets. Mayor decided to limit the competition only to running events andasked you for help with planning their tracks.

There are n street junctions and n − 1 streets in Bytetown. From each junction there is a path leadingto every other junction. Every running track must start at some junction, lead along some streets andfinish at some other junction. Mayor would like to organize as many events simultaneously as possible,so the number of tracks should be maximized. Due to safety reasons no two tracks may have a commonjunction or street. Additionally, not every junction can be used as a starting or ending point of an event.

一棵树，给定一些选定的点从中选取起点和终点，要求所有路径没有共点、共边。问最多多少条这样的路径。

直接DP，从叶子向上推，若某点和他的子树有2个或以上未配对的点，配成一对并把没配对的点数清零。若某点有一个未配对的点，把这个点数加到父亲节点上。

#include <cstdio>
#include <iostream>
#include <string.h>
#include <string> 
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <bitset>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn=200005,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f; 
const ld pi=acos(-1.0L);
int head[maxn],match[maxn];
int num,ans;
bool visit[maxn],mark[maxn];

struct Edge {
	int from,to,pre;
};
Edge edge[maxn*2];

void addedge(int from,int to) {
	edge[num]=(Edge){from,to,head[from]};
	head[from]=num++;
	edge[num]=(Edge){to,from,head[to]};
	head[to]=num++;
}

bool dfs(int now) {
	visit[now]=1;
	match[now]=0;
	if (mark[now]) match[now]++;
	for (int i=head[now];i!=-1;i=edge[i].pre) {
		int to=edge[i].to;
		if (!visit[to]) {
			match[now]+=dfs(to);
		}
	}
	if (match[now]==1) return true;
	if (match[now]==0) return false;
	ans++;
	return false;
}

int main() {
	freopen("athletic.in","r",stdin);	
	freopen("athletic.out","w",stdout);	
	num=0;mem0(visit);
	memset(head,-1,sizeof(head));
	ans=0;
	int n,m,i,x,y;
	scanf("%d",&n);
	for (i=1;i<n;i++) {
		scanf("%d%d",&x,&y);
		addedge(x,y);
	}
	scanf("%d",&m);
	mem0(mark);
	for (i=1;i<=m;i++) {
		scanf("%d",&x);
		mark[x]=1;
	}
	dfs(1);
	printf("%d\n",ans);
	return 0;
}

本文标签： 树型GymcodeforcesDPcompetition