类直径树上贪心

http://cplusoj.com/d/senior/p/SS231109C

场上想到枚举点，然后最大值为高，然后可以求最大值。但是感觉计数会重

---

计数其实不会重，如图中，红色线段显然比蓝色线段优

所以我们枚举3叉点时没错的

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL#define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else#define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 500010
//#define M
//#define mo
struct node {int mx, cnt; void init() { mx=-1e15; cnt=0; }node operator +(const node &A) const {if(A.mx>mx) return A; if(mx>A.mx) return (*this); return {mx, cnt+A.cnt}; }node add() { node A=(*this); A.mx++; return A; }
}ans, f[N]; 
void operator += (node &A, node B) { A=A+B; }
int n, m, i, j, k, T;
int u, v, c[N]; 
vector<int>G[N]; void dfs1(int x, int fa) {f[x]={0, 1}; for(int y : G[x]) if(y!=fa) {dfs1(y, x); f[x]+=f[y].add(); }debug("> %lld : %lld %lld\n", x, f[x].mx, f[x].cnt); 
}void dfs2(int x, int fa, node p) {debug("Shang %lld : %lld %lld\n", x, p.mx, p.cnt); int z=G[x].size(), i, j, k=0; vector<node>pre, lst, cao; node dp[3][2], ndp[3][2];vector<int>ve; pre.resize(z+2); lst.resize(z+2); ve.resize(z+2); for(auto &t : pre) t.init(); for(auto &t : lst) t.init(); for(auto y : G[x]) if(y!=fa) ve[++k]=y; pre[0]=p; for(i=1; i<=k; ++i) pre[i]=pre[i-1]+f[ve[i]].add(); for(i=k; i>=1; --i) lst[i]=lst[i+1]+f[ve[i]].add(); for(i=1; i<=k; ++i) dfs2(ve[i], x, (pre[i-1]+lst[i+1]).add()); if(c[x]<3) return ; int mx=pre[k].mx; debug("[%lld] %lld\n", k, mx); for(i=1; i<=k; ++i) cao.pb(f[ve[i]].add()); cao.pb(p); for(i=0; i<=2; ++i) for(j=0; j<=1; ++j) dp[i][j].init(); dp[0][0]={0, 1}; for(auto t : cao) {debug("# %lld %lld\n", t.mx, t.cnt); for(i=0; i<=2; ++i) for(j=0; j<=1; ++j) ndp[i][j].init(); for(i=0; i<=2; ++i) for(j=0; j<=1; ++j) {ndp[i][j|(t.mx==mx)]+=dp[i][j]; if(i<2) {node cur = {dp[i][j].mx+mx*t.mx, dp[i][j].cnt*t.cnt}; debug("** %lld(%lld %lld) %lld | %lld\n", cur.mx, dp[i][j].mx, mx*t.mx, cur.cnt, j); ndp[i+1][j]+=cur; }}for(i=0; i<=2; ++i) for(j=0; j<=1; ++j) dp[i][j]=ndp[i][j]; }debug("=# %lld %lld\n", dp[2][1].mx, dp[2][1].cnt); ans+=dp[2][1]; 
}signed main()
{freopen("tree.in", "r", stdin);freopen("tree.out", "w", stdout);#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif
//	T=read();
//	while(T--) {
//
//	}	n=read(); for(i=1; i<n; ++i) {u=read(); v=read(); G[u].pb(v); G[v].pb(u); ++c[u]; ++c[v]; k=max(k, c[u]); k=max(k, c[v]); }if(k<=2) return printf("0 1"), 0; node p; p.init(); dfs1(1, 0); dfs2(1, 0, {0, 1}); printf("%lld %lld\n", ans.mx, ans.cnt); return 0;
}