题目传送门
题意：
n个点，n-1条边，其实就是给一棵树，让你求添加最多的边数，使得添加边的树构成的新图是一个二分图，当然不能有重边，有的话，可以添加无穷多条边。
晚上没有打，早上来补题。。。
思路：
我是这样想的，树肯定是二分图啦。
我就先把无根树（无向）变成以结点1为根的有根树（有向），再计算出这个树变成二分图的两个集合的任意一个集合的点数node，可以得到添加最多的边数=node*(n-node)-(n-1)；因为二分图有两个集合，一个集里面的结点不能互相连边，只能向另一个集合连边，所以可以连node*(n-node)条边，再减去原来树的边数，就是最多的。
原来的无根树变成有根树，并且有向。
有根树变成二分图，我们就是求点数，没必要存储图，这样其实就很简单了，就是一个深度问题，也就是层度问题，自己可以画一画，因为树没有环。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=1e5+10;
vector<int>G[maxn],Tree[maxn];
int pre[maxn];
int cnt_node;
void match_node(int u,int type)
{
int len=Tree[u].size();
if(type%2)
cnt_node++;
for(int i=0;i<len;i++)
{
match_node(Tree[u][i],type+1);
}
}
void node_tree(int u,int fu)
{
int len=G[u].size();
for(int i=0;i<len;i++)
{
if(G[u][i]==fu)
continue;
if(pre[G[u][i]]==0)
{
Tree[u].push_back(G[u][i]);
node_tree(G[u][i],u);
}
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
memset(pre,0,sizeof(pre));
pre[1]=-1;
node_tree(1,-1);
cnt_node=0;
match_node(1,1);
printf("%I64d\n",(long long)cnt_node*(n-cnt_node)-(n-1));
}