\(\mathcal{Description}\)
\(\mathcal{Solution}\)
根据题意，我们知道
根节点深度为1，深度为 奇数 的节点由\(David\)移动，我们称为\(D\)点，深度为 偶数 的节点由\(Vincent\)移动，我们称为\(V\)点
记\(big[i],sma[i]\)表示\(i\)节点以为根节点，由\(i\)开始移动，最后到叶子节点时的数字由\(David\)放数字 最大是第几大的数字 ，由\(Vincent\)放数字__最小是第几小的数字__
假如\(i\)节点是\(D\)点
那么对于\(i\)的儿子\(v\),有
- \(big[i]=min\{big[i],big[v]\}\)
因为\(David\)移动到叶子节点时尽量要最大的数字，显然往儿子节点移动时，往到叶子节点时能得到最大数的排名最高的儿子移动最好，由于是\(David\)放数字，所以\(David\)不会将最优的数字浪费在他不会移动到的点
- \(sma[i]+=sma[v]\)
我们知道\(sma[v]\)，若由\(D\)向\(V\)移动，那么此时\(sma[i]\)就至少是\(sma[v]\)
若\(D\)向另外的儿子\(V’\)移动，考虑为什么不往\(V\)移动：
因为向\(V\)移动后\(Vincent\)肯定会尽量使结果对其最优，所以\(Vincent\)会把对他而言最优的数字放在那边，聪明的\(David\)发现后就不会往这边走了，那为什么要把最优数字放在\(V\)呢，同理，\(David\)会发现往其他地方移动没有往\(V\)更优，就会往\(V\)移动了，而为什么\(Vincent\)要让\(David\)只能往\(V’\)移动呢，因为如果\(Vincent\)让\(David\)往\(V\)移动的话得到的最终结果对\(Vincent\)就不是最优的了。这么说可能有点绕，但都是必然的因果关系，主要我们要在为\(David\)考虑时，还要换位思考\(Vincent\)的想法，可以画个图想想。
所以\(David\)会把最优的一些数字放在\(V\)之类的其他点，而这样\(Vincent\)就会往\(V’\)走，所以就会浪费掉除\(sma[v’]\)以外个\(sma[v]\)个大数字，又此时往\(V’\)移动得到的最优数字是第\(big[v’]\)，所以要加上所有儿子的\(sma\)
假如\(i\)节点是\(V\)点
那么此时的情况和\(D\)点相反，因为他们的目的相反，所以
对于\(i\)的儿子\(v\)有
- \(big[i]+=big[v]\)
- \(sma[i]=min\{sma[i],sma[v]\}\)
代码
/*******************************
Author:Morning_Glory
LANG:C++
Created Time:2019年06月20日 星期四 15时27分03秒
*******************************/
#include <cstdio>
#include <fstream>
using namespace std;
const int maxn = 100005;
//{{{cin 快读
struct IO{
template<typename T>
IO & operator>>(T&res){
res=0;
bool flag=false;
char ch;
while((ch=getchar())>'9'||ch<'0') flag|=ch=='-';
while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
if (flag) res=~res+1;
return *this;
}
}cin;
//}}}
int n,m,u,v,root,cnt;
int head[maxn],to[maxn],nxt[maxn];
int big[maxn],sma[maxn],fa[maxn],col[maxn];//col[i]=1 -> David
//{{{add
void add (int u,int v)
{
nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v,fa[v]=u;
}
//}}}
void dfs (int x)
{
col[x]=!col[fa[x]];
if (!head[x]){
++m;
big[x]=sma[x]=1;
return;
}
if (col[x])big[x]=n+1;
elsesma[x]=n+1;
for (int e=head[x];e;e=nxt[e]){
dfs(to[e]);
if (col[x]){
big[x]=min(big[x],big[to[e]]);
sma[x]+=sma[to[e]];
}
else{
big[x]+=big[to[e]];
sma[x]=min(sma[x],sma[to[e]]);
}
}
}
int main()
{
cin>>n;
for (int i=1;i<=n-1;++i){
cin>>u>>v;
add(u,v);
}
for (int i=1;i<=n&&!root;++i)
if (!fa[i])root=i;
dfs(root);
printf("%d %d\n",m-big[root]+1,sma[root]);
return 0;
}
