Codeforces Round 915 (Div. 2)

A. Constructive Problems

看了一眼数据，猜测可能是n,m里的最大

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int a,b;
	cin>>a>>b;
	int ans=max(a,b);
	cout<<ans<<"\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t=1;
	cin>>t;
	for(int i=1;i<=t;i++)solve();
	return 0;
} 

ahhhhh

B. Begginer's Zelda

题意：给定一棵树，你可以的操作是选择两个节点，将两个节点中间的所有节点（包括）变成一个节点，问你最少操作多少次能将树变成一个节点。

大概想了一下，应该是叶子节点的个数/2向上取整

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int>a[N];
int vis[N];
int cnt=0;
void dfs(int x){
	if(vis[x])return;
	vis[x]=1;
	if(a[x].size()==1)cnt++;
	for(auto c:a[x]){
		dfs(c);
	}
}
void solve(){
	int n;
	cin>>n;
	cnt=0;
	for(int i=1;i<=n;i++){
		a[i].clear();
		vis[i]=0;
	}
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin>>u>>v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	dfs(1);
	int ans=(cnt+1)/2;
	cout<<ans<<"\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t=1;
	cin>>t;
	for(int i=1;i<=t;i++)solve();
	return 0;
}