C – Bob in Wonderland

发布于 2020-10-09  392 次阅读




Bob in Wonderland

A chain, as everybody knows, is made of connected links. Typically, all links are of the sameshape and size. Bob is a blacksmith apprentice, and he is making his own first iridium chain.He follows the traditional formula of chain-making. It says:

• If there is no chain yet, make a link and it will be a piece of your chain.

• If there is a piece of chain, make another link and connect it to one other link in the pieceof chain you already have.

Bob made the first link. Then, each time he made another link, he connected it to some otherlink in his piece of chain, exactly as the formula told him to do.

When he finished, he realized that the object he created did not resemble a usual chain at all.In an effort to straighten the chain, he repeatedly took two links which seemed to be at the endsof the chain and tried to pull them apart as far as he could. But there were some more piecesof the “chain” dangling down from the straightened piece at various places.

It was obvious to Bob that his work is not finished yet and he decided to call the object heproduced the unfinished chain. After some more pondering, Bob came to a conclusion that hehas to break some links and reconnect them to the rest of the unfinished chain more cautiouslyto obtain a straight chain he aims to produce. In a straight chain, each link is connected to atmost two other links and a straight chain cannot be separated into more pieces without breakinga link.

Being now more careful, Bob is going to progress in simple steps. In one step he will choose alink, say A, connected to another link, say B, in the unfinished chain. He will then break A,disconnect it from B and reconnect A to some other link, say C, in the unfinished chain. Ifthere are more links other than B originally connected to A, Bob will keep them connected toA during the whole step.

What is the minimum number of steps Bob has to perform to get a straight chain?

Input Specification

The first line contains one integer N(1≤N≤3⋅105), the number of links in the unfinishedchain. The links are labeled 1,2,…,N. Each of the next N−1 lines has two integers denotingthe labels of two connected links in the unfinished chain. The connections are listed in arbitraryorder. The unfinished chain is guaranteed to form only one piece.

Output Specification

Output the minimum number of steps which will turn Bob’s unfinished chain into a straightchain.

2`YHSIS1E_$KOH}ZFZ5UBWR.png
Sample Input
5
4 3
1 2
4 5
3 2

Sample Output
0

Sample Input 2
6
1 3
3 2
3 4
4 5
4 6

Sample Output 2
2

Sample Input 3
7
1 2
2 3
3 4
4 5
3 6
6 7

Sample Output 3
1

题意:给定n条链子,以及它们的n-1条链接关系,求把这n条链子改成链成一条直链最少需要多少步。
思路:记录每个节点的个数,超过2则代表该点有2个以上的出度,即该点一定有多个环,将该点的数量-2,累加每个这样的点,即是最后的多余环数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[400005]={0};
int main() {
	int n,sum=0,b,c;
	scanf("%d",&n);
	for(int i=1; i<n; i++) {
		scanf("%d%d",&b,&c);
		a[b]++;
		a[c]++;
	}
	for(int i=1; i<=n; i++) {
		if(a[i]>2)sum+=a[i]-2;
		}
		printf("%d",sum);
	return 0;
}