# 洛谷—— P3576 [POI2014]MRO-Ant colony

## 题目描述

The ants are scavenging an abandoned ant hill in search of food.

The ant hill has nn chambers and n-1n−1 corridors connecting them.

We know that each chamber can be reached via a unique path from every other chamber.

In other words, the chambers and the corridors form a tree.

There is an entrance to the ant hill in every chamber with only one corridor leading into (or out of) it.

At each entry, there are gg groups of m_1,m_2,\cdots,m_gm?1??,m?2??,?,m?g?? ants respectively.

These groups will enter the ant hill one after another, each successive group entering once there are no ants inside.

Inside the hill, the ants explore it in the following way:

• Upon entering a chamber with dd outgoing corridors yet unexplored by the group,the group divides into dd groups of equal size. Each newly created group follows one of the d corridors.If d=0d=0, then the group exits the ant hill.
• If the ants cannot divide into equal groups, then the stronger ants eat the weaker until a perfect division is possible.Note that such a division is always possible since eventually the number of ants drops down to zero.Nothing can stop the ants from allowing divisibility - in particular, an ant can eat itself, and the last one remaining will do so if the group is smaller than dd.

The following figure depicts mm ants upon entering a chamber with three outgoing unexplored corridors, dividing themselves into three (equal) groups of \left \lfloor m/3 \right \rfloor⌊m/3⌋ ants each. A hungry anteater dug into one of the corridors and can now eat all the ants passing through it.

However, just like the ants, the anteater is very picky when it comes to numbers.

It will devour a passing group if and only if it consists of exactly kk ants.

We want to know how many ants the anteater will eat.

## 输入输出格式

The first line of the standard input contains three integers nn, gg, kk(2\le n,g\le 1\ 000\ 0002≤n,g≤1 000 000, 1\le k\le 10^91≤k≤10?9??), separated by single spaces.

These specify the number of chambers, the number of ant groups and the number of ants the anteater devours at once. The chambers are numbered from 1 to nn.

The second line contains gg integers m_1,m_2,\cdots,m_gm?1??,m?2??,?,m?g?? (1\le m_i\le 10^91≤m?i??≤10?9??), separated by single spaces, where m_im?i?? gives the number of ants in the ii-th group at every entrance to the ant hill. The n-1n−1 lines that follow describe the corridors within the ant hill;the ii-th such line contains two integers a_ia?i??,b_ib?i?? (1\le a_i,b_i\le n1≤a?i??,b?i??≤n), separated by a single space, that indicate that the chambers no. a_ia?i?? and b_ib?i?? are linked by a corridor. The anteater has dug into the corridor that appears first on input.

Your program should print to the standard output a single line containing a single integer: the number of ants eaten by the anteater. ## 输入输出样例

7 5 3
3 4 1 9 11
1 2
1 4
4 3
4 5
4 6
6 7


21


## 说明

 1 #include <algorithm>
2 #include <cstdio>
3
4 #define LL long long
5 const int N(1000005);
6 inline void read(LL &x)
7 {
8     x=0; register char ch=getchar();
9     for(; ch>‘9‘||ch<‘0‘; ) ch=getchar();
10     for(; ch>=‘0‘&&ch<=‘9‘; ch=getchar()) x=x*10+ch-‘0‘;
11 }
12 LL n,g,k,s1,s2,gi[N];
13 int head[N],sumedge;
14 struct Edge {
15     int v,next;
16     Edge(int v=0,int next=0):v(v),next(next){}
17 }edge[N<<1];
18 inline void ins(int u,int v)
19 {
20     edge[++sumedge]=Edge(v,head[u]);
21     head[u]=sumedge;
22     edge[++sumedge]=Edge(u,head[v]);
23     head[v]=sumedge;
24 }
25
26 #define min(a,b) (a<b?a:b)
27 #define max(a,b) (a>b?a:b)
28 int du[N],dad[N],minn[N],maxx[N];
29 void DFS(int u)
30 {
31     for(int v,i=head[u]; i; i=edge[i].next)
32     {
33         v=edge[i].v;
34         if(dad[u]==v) continue;
35         dad[v]=u; du[u]++;
36     }
37     for(int v,i=head[u]; i; i=edge[i].next)
38     {
39         v=edge[i].v;
40         if(dad[u]==v) continue;
41         minn[v]=minn[u]*du[u];
42         maxx[v]=(maxx[u]+1)*du[u]-1;
43         maxx[v]=min(maxx[v],gi[g]);
44         if(minn[v]<=gi[g]) DFS(v);
45     }
46 }
47
48 LL l,r,mid,ans;
49 LL check(LL x)
50 {
51     LL ret=0;
52     for(l=1,r=g; l<=r; )
53     {
54         mid=l+r>>1;
55         if(gi[mid]<x)
56         {
57             ret=mid;
58             l=mid+1;
59         }
60         else r=mid-1;
61     }
62     return ret;
63 }
64
65 int Presist()
66 {
67     read(n),read(g),read(k);
68     for(int i=1; i<=g; ++i) read(gi[i]);
69     read(s1);read(s2);
70     for(LL u,v,i=2; i<n; ++i)
71         read(u),read(v),ins(u,v);
72     std::sort(gi+1,gi+g+1);
73     maxx[s1]=maxx[s2]=minn[s1]=minn[s2]=k;
74     DFS(s1); DFS(s2);
75     for(int i=1; i<=n; ++i)
76         if(!du[i]) ans+=check(maxx[i]+1)-check(minn[i]);
77     printf("%lld\n",ans*k);
78     return 0;
79 }
80
81 int Aptal=Presist();
82 int main(){;}

## 洛谷1231 教辅的组成 ## 洛谷 P3367 并查集模板

#include<cstdio> using namespace std; int n,m,p; int father; int find(int x) { if(father[x]!=x) father[x]=find(father[x]); return father[x]; } void unionn(int i,int j) { father[j]=i; } int main() { scanf("%d%d",&n,&m); for

## [题解]洛谷比赛『期末考后的休闲比赛2』 [前言] 这场比赛已经结束了有几天,但我各种忙,虽然AK但还是没来得及写题解.(我才不会告诉你我跑去学数据结构了) T1 区间方差 (就不贴题好了) 首先可以推公式(我们可以知道,线段树然而并不能通过初中学过的方差公式在log(L)内求出方差): (s2表示方差,L表示区间长度,xi表示区间的每一项,最后一个x上画了一根线表示这些数据的平均数) 用二项式定理完全平方公式可得: 再次展开: 另外,再代入以下这个 得到了: 然后继续吧.. 然后duang地一声合并同类项,于是我们得到了: 然后可以高