题意翻译
给你一棵树,每次挑选这棵树的两个叶子,加上他们之间的边数(距离),然后将其中一个点去掉,问你边数(距离)之和最大可以是多少.
题目描述
You are given an unweighted tree with n n n vertices. Then n−1 n-1 n−1 following operations are applied to the tree. A single operation consists of the following steps:
- choose two leaves;
- add the length of the simple path between them to the answer;
- remove one of the chosen leaves from the tree.
Initial answer (before applying operations) is 0 0 0 . Obviously after n−1 n-1 n−1 such operations the tree will consist of a single vertex.
Calculate the maximal possible answer you can achieve, and construct a sequence of operations that allows you to achieve this answer!
输入输出格式
输入格式：
The first line contains one integer number n n n ( 2<=n<=2⋅105 2<=n<=2·10^{5} 2<=n<=2⋅105 ) — the number of vertices in the tree.
Next n−1 n-1 n−1 lines describe the edges of the tree in form ai,bi a_{i},b_{i} ai,bi ( 1<=ai 1<=a_{i} 1<=ai , bi<=n b_{i}<=n bi<=n , ai≠bi a_{i}≠b_{i} ai≠bi ). It is guaranteed that given graph is a tree.
输出格式：
In the first line print one integer number — maximal possible answer.
In the next n−1 n-1 n−1 lines print the operations in order of their applying in format ai,bi,ci a_{i},b_{i},c_{i} ai,bi,ci , where ai,bi a_{i},b_{i} ai,bi — pair of the leaves that are chosen in the current operation ( 1<=ai 1<=a_{i} 1<=ai , bi<=n b_{i}<=n bi<=n ), ci c_{i} ci ( 1<=ci<=n 1<=c_{i}<=n 1<=ci<=n , ci=ai c_{i}=a_{i} ci=ai or ci=bi c_{i}=b_{i} ci=bi ) — choosen leaf that is removed from the tree in the current operation.
See the examples for better understanding.
输入输出样例
3
1 2
1 3
3
2 3 3
2 1 1
5
1 2
1 3
2 4
2 5
9
3 5 5
4 3 3
4 1 1
4 2 2
Solution：
昨天学长讲课的题目，思路贼有意思。
我们先打表$O(n^3)$枚举答案，枚举到$n=11$时会发现后面答案每次加$49$，这样就可以直接乱搞了。
代码：
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define il inline
#define ll long long
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
using namespace std;
using namespace __gnu_pbds;
int n;
ll ans;
gp_hash_table<int,bool>mp; il int solve(int x){
int ans,tot=;
for(int i=;i<=x;i++) for(int j=;i+j<=x;j++) for(int k=;i+j+k<=x;k++){
ans=i+j*+k*+(x-i-j-k)*;
if(!mp[ans]) mp[ans]=,tot++;
}
return tot;
} int main(){
ios::sync_with_stdio();
cin>>n;
n<=?printf("%d\n",solve(n)):printf("%lld\n",solve()+1ll*(n-)*);
return ;
}