2017年12月

luogu2123 皇后游戏

把边按照$a_i$升序排序。

每次加入一条边，如果两端不连通，则直接加入，否则加入以后就会出现一个环，割掉这个环上$b_i$最大的边。

每次加入一条边后计算当前答案取最大值。

有n个村庄，连成一棵树。

有m次操作，每次形如$u,v,w$,表示给从u到v的所有村庄颁发一个类型为w的证书，求每个村庄得到哪类证书的个数最多。若有多个输出类型最小值，若没有证书输出0

$n,m,w\le 10^5$

给定一棵n点的树，每个点有点权$w_i$。每次给定u,v，求$(\sum_{i=1}^n\sum_{j=1}^nf(i,j)) \mod 10^9+7$，其中当i到j的路径和u到v的路径有交集时$f(i,j)=w_iw_j$，否则$f(i,j)=0$