题目链接:http://codeforces.com/problemset/problem/765/E
$DFS子$树进行$DP$
大概分以下几种情况:
1.为叶子,直接返回。
2.长度不同的路径长度只有一条,显然可以合并成这一条的长度。
3.长度不同的路径长度有两条,并且这个点为根,显然可以合并成这两条的长度和。
4.其他的都不合法。
注意:事实上如果第一次$DP$之后不合法要考虑换根再做一次
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<set>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 1001000
#define llg long long
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m,root;
vector<llg>a[maxn]; inline int getint()
{
int w=,q=; char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar(); if(c=='-') q=,c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;
} void init()
{
llg x,y;
cin>>n;
for (llg i=;i<n;i++)
{
x=getint(),y=getint();
a[x].push_back(y),a[y].push_back(x);
}
} llg dfs(llg x,llg fa)
{
set<llg>s;
llg w=a[x].size(),v;
for (llg i=;i<w;i++)
{
v=a[x][i];
if (v==fa) continue;
llg val=dfs(v,x);
if (val==-) return val;
s.insert(val+);
}
if (s.size()==) return *s.begin();
if (s.size()==) return ;
if (s.size()==)
{
if (fa) {root=x; return -;}
return *s.begin()+*s.rbegin();
}
return -;
} int main()
{
yyj("tree");
init();
llg ans=dfs(,);
if (ans==- && root) ans=dfs(root,);
while (ans%==) ans/=;
cout<<ans;
return ;
}