题目大意：

　　给定一棵$n(n\le10^6)$个结点的树。在每个叶子结点，有$g$群蚂蚁要从外面进来，其中第$i$群有$m_i$只蚂蚁。这些蚂蚁依次爬树（一群蚂蚁爬完后才会爬另一群），若当前经过结点度为$d+1$，蚂蚁数量为$m$，则接下来没走过的$d$个方向，每个方向爬$\lfloor\frac md\rfloor$只蚂蚁，剩下蚂蚁消失。在给定的一条边上有一只食蚁兽，若当前经过这条边的蚂蚁数量为$k$，则吃掉这些蚂蚁。问最后能吃到多少蚂蚁？

思路：

　　从给定边出发BFS，算出每条边会被吃掉的蚁群规模的上界和下界。若到了叶子节点，就在$\{m_i\}$中二分。然后洛谷和SZKOpuł上都能随便AC，BZOJ大力卡一波常才过。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 typedef long long int64; 6 class BufferedInputStream { 7     private: 8         char *buf,*p; 9         int size;10     public:11         BufferedInputStream() {12             register int fd=fileno(stdin);13             struct stat sb;14             fstat(fd,&sb);15             size=sb.st_size;16             p=buf=reinterpret_cast
         
          (mmap(0,size,PROT_READ,MAP_PRIVATE,fileno(stdin),0));17         }18         char getchar() {19             return (p==buf+size||*p==EOF)?EOF:*p++;20         }21 };22 BufferedInputStream in;23 inline int getint() {24     register char ch;25     while(!__builtin_isdigit(ch=in.getchar()));26     register int x=ch^'0';27     while(__builtin_isdigit(ch=in.getchar())) x=(((x<<2)+x)<<1)+(ch^'0');28     return x;29 }30 const int N=1e6+1;31 bool vis[N];32 int deg[N],q[N],head,tail,h[N],sz;33 int64 m[N],max[N],min[N];34 struct Edge {35     int to,next;36 };37 Edge e[N<<1];38 inline void add_edge(const int &u,const int &v) {39     e[++sz]=(Edge){v,h[u]};h[u]=sz;deg[u]++;40     e[++sz]=(Edge){u,h[v]};h[v]=sz;deg[v]++;41 }42 int main() {43     const int n=getint(),g=getint(),k=getint();44     int64 lim=0;45     for(register int i=1;i<=g;i++) {46         lim=std::max(lim,m[i]=getint());47     }48     std::sort(&m[1],&m[g]+1);49     for(register int i=1;i