类直径树上贪心

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134317828

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

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

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

在这里插入图片描述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#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 LOCAL
	  freopen("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;
}