BZOJ 4543 Hotel

发表于 | 更新于

Link

Solution

Tips

如果要把内存分配处理的精细一些还是有点繁的(当然仅仅对我这种juruo) g[]g[]要开两倍。。(好吧我知道地球人都知道但是我刚知道。。)

Code

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
108
#include "lucida"
using std::pair;
using std::make_pair;
const int MAXN=100000+11;
struct Edge {
	int to,v;
	Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void *operator new(size_t) {
		static Edge *Pool=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*Me=Pool;
		return Me++;
	}
};
struct Graph {
	Edge *head;
	void App(int to) {
		head=new Edge(to,head);
	}
	operator Edge*(){
		return head;
	}
}G[MAXN];
int64 *f[MAXN],*g[MAXN];
pair<int64*,int64*> alloc(size_t cnt) {
	//os<<'['<<cnt<<"]\n";

	static const int SIZE=MAXN<<2;
	static int64 *Pool=new int64[SIZE](),*Me=Pool,*re;
	return re=Me,Me+=cnt,make_pair(re,Me-1);
	//+=cnt?
}
int prefer[MAXN],fa[MAXN],chd[MAXN]={-1};
void DFS(int pos) {
	for(Edge *e=G[pos];e;e=e->pre)
		if(e->to!=fa[pos]) {
			int u=e->to;
			fa[u]=pos;
			DFS(u);
			if(chd[u]>chd[prefer[pos]])
				prefer[pos]=u;
		}
	chd[pos]=chd[prefer[pos]]+1;
}
void Alloc(int pos,int len) {

//	os<<pos<<':'<<len<<'\n';

	if(!prefer[pos]) {
		f[pos]=alloc(len).second;
		g[pos]=alloc(len<<1).first;//没有开两倍
	} else {
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=fa[pos]) {
				int u=e->to;
				Alloc(u,(u==prefer[pos])*len+1);
			}
	}
}
int64 DP(int pos) { 
	int64 res=0;
	if(!prefer[pos]) {
		f[pos][0]=1;
	} else {
		int u;
		for(Edge *e=G[pos];e;e=e->pre)
			if((u=e->to)!=fa[pos]) 
				res+=DP(u);
		u=prefer[pos];
		f[pos]=f[u]-1;
		g[pos]=g[u]+1;
		f[pos][0]=1;
		res+=g[pos][0];
		for(Edge *e=G[pos];e;e=e->pre)
			if((u=e->to)!=fa[pos] && u!=prefer[pos]) {
				for(int d=0;d<=chd[u]+1;++d) {
					if(d>=1)
						res+=g[pos][d]*f[u][d-1];
					if(d<=chd[u]-1)
						res+=f[pos][d]*g[u][d+1];
				}
				for(int d=0;d<=chd[u]+1;++d) {
					if(d>=1) {
						g[pos][d]+=f[pos][d]*f[u][d-1];
						f[pos][d]+=f[u][d-1];
					}
					if(d<=chd[u]-1)
						g[pos][d]+=g[u][d+1];
				}
			}
	}
	//os<<pos<<':'<<res<<'\n';
	return res;
}
int main() {
	//freopen("input","r",stdin);
	int n;is>>n;
	for(int i=1;i<=n-1;++i) {
		int x,y;
		is>>x>>y;
		G[x].App(y);
		G[y].App(x);
	}
	DFS(1);
	Alloc(1,1);
	int64 Ans=DP(1);
	os<<Ans<<'\n';
	return 0;
}