BZOJ 3872 Ant colony

发表于 | 更新于

Link

Solution

真的是叶节点！好吧当我没说 只要知道某一条边需要多少蚂蚁流过就可以了，然而这个流量的取值是一个区间，所以要维护一个区间。一开始naive只维护了最小值。 如果知道了一个点的树边上需要流[l,r][l,r]，那么这个点就需要有[deg[u]∗l,(deg[u]+1)∗r−1][deg[u]*l,(deg[u]+1)*r-1]，它下面的边需要有[(deg[u]−1)∗l,(deg[u]−1)∗(r+1)−1][(deg[u]-1)*l,(deg[u]-1)*(r+1)-1]。 注意，即使不乘kk，合法的群数也会爆int。

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
#include "lucida"
using std::sort;
using std::lower_bound;
using std::upper_bound;
const int MAXN=1000000+11;
struct Edge {
	int to;
	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 EdgeList {
	Edge *head;int deg;
	void App(int to) {
		head=new Edge(to,head);
		++deg;
	}
	operator Edge*() {
		return head;
	}
}G[MAXN];
void Adde(int f,int t) {
	G[f].App(t);
	G[t].App(f);
}
int UPLIM,c[MAXN],cc;
int count(int64 L,int64 R) {
	/*int cnt=0;
	for(int i=L;i<=R;++i)
		cnt+=ext[i];*/
	int p1=lower_bound(c+1,c+1+cc,L)-c,
		p2=upper_bound(c+1,c+1+cc,R)-c-1;
	if(p1==cc+1)
		return 0;
	else
		return p2-p1+1;
}
bool ud[MAXN];
int64 DFS(int pos,int64 lbd,int64 ubd) {

//	os<<'{'<<pos<<'}'<<lbd<<' '<<ubd<<'\n';

	if(lbd>UPLIM)
		return 0;
	chkmn(ubd,(int64)UPLIM);
	ud[pos]=1;
	int64 res=(G[pos].deg==1?count(lbd*G[pos].deg,(ubd+1)*G[pos].deg-1):0);
	lbd=lbd*(G[pos].deg-1);
	ubd=(ubd+1)*(G[pos].deg-1)-1;
	for(Edge *e=G[pos];e;e=e->pre)
		if(!ud[e->to]) {
			int u=e->to;
			res+=DFS(u,lbd,ubd);
		}
	return res;
}
int main() {
//	freopen("input","r",stdin);
	int n,K;is>>n>>cc>>K;
	for(int i=1;i<=cc;++i) {
		is>>c[i];
		//ext.Insert(c[i]);ext[c[i]]=1;
		chkmx(UPLIM,c[i]);
	}
	sort(c+1,c+1+cc);
	int from,to;
	for(int i=1;i<=n-1;++i) {
		int x,y;
		is>>x>>y;
		Adde(x,y);
		if(i==1) {
			from=x;
			to=y;
		}
	}
	int64 Ans=0;
	ud[from]=1,ud[to]=0;Ans+=DFS(to,K,K);
	ud[to]=1,ud[from]=0;Ans+=DFS(from,K,K);
	os<<(int64)Ans*K<<'\n';
	return 0;
}
/*
 * 题意读错了
 * 数量爆ll了
 */