题意
给你(n)个点的树,边有边权
问使得所有的点度数都小于等于(x)的最小删边的代价 ([x in 0...n-1])
题解
首先对于每个(x)
可以有一个(O(nlogn))的做法
就是设(f[u][0/1])表示不选择/选择点(u)的最小代价
那么就是把所有儿子按照(f[v][1]+w-f[v][0])排序
然后(f[u][0])就是选择至少前(d[u]-x)小的(f[v][1]+w),其他选择(min(f[v][1]+w,f[v][0]))
同理,(f[u][1])就是选择至少前(d[u]-x-1)小的
其实这个可以通过对于所有儿子都是加上(f[v][0])
然后把(f[v][1]+w-f[v][0])加入小根堆并选择至少(d[u]-x)个来实现
然后我们可以发现随着(x)的增加,合法的点数越来越少
那么我们可以每次只考虑合法的点,把不合法的点的边权加入父节点中然后删除
然后遍历合法儿子的时候也是把(f[v][1]+w-f[v][0])加入父节点中
那么问题就是找到至少前(d[u]-x)小的最小值的和
平衡树即可解决
每次遍历合法点的复杂度是
(sum_{i=0}^{n-1}sum_{j=1}^{n}[ile d_j])
然而一棵树的(d_i)和为(n imes 2-2)
所以遍历的总复杂度是(O(n))
代码
#include<queue>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
# define LL long long
const int M = 250005 ;
const LL INF = 1e16 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
int vis[M] ;
int n , num , hea[M] ;
int d[M] , pi[M] , fdis[M] , fa[M] ;
int Tag , dmx , rt[M] ;
LL ans , f[M][2] ;
struct Node { int v , w ; } ;
inline bool operator < (Node A , Node B) {
return d[A.v] > d[B.v] ;
}
vector < Node > vec[M] ;
inline bool cmp(int a , int b) {
return d[a] < d[b] ;
}
inline void add_edge(int u , int v , int w) {
vec[u].push_back((Node) { v , w }) ;
}
void fdfs(int u , int father) {
fa[u] = father ;
for(int i = 0 , v , w , sz = vec[u].size() ; i < sz ; i ++) {
v = vec[u][i].v , w = vec[u][i].w ; if(v == father) continue ;
fdis[v] = w ; fdfs(v , u) ;
}
}
namespace fhq {
# define ls (son[now][0])
# define rs (son[now][1])
int tot ;
LL sum[M * 8] , val[M * 8] ;
int size[M * 8] , pos[M * 8] , son[M * 8][2] ;
inline int New(LL w) {
size[++tot] = 1 ; pos[tot] = rand() ;
sum[tot] = w ; val[tot] = w ; return tot ;
}
inline void pushup(int now) {
size[now] = size[ls] + size[rs] + 1 ;
sum[now] = sum[ls] + sum[rs] + val[now] ;
}
int Merge(int x , int y) {
if(!x || !y) return x + y ;
if(pos[x] < pos[y]) {
son[x][1] = Merge(son[x][1] , y) ;
pushup(x) ; return x ;
}
else {
son[y][0] = Merge(x , son[y][0]) ;
pushup(y) ; return y ;
}
}
void Split(int now , LL k , int &x , int &y) {
if(!now) return (void)(x = y = 0) ;
if(val[now] <= k) {
x = now ;
Split(rs , k , rs , y) ;
}
else {
y = now ;
Split(ls , k , x , ls) ;
}
pushup(now) ;
}
inline void Insert(int &root , LL w) {
int x , y ;
Split(root , w , x , y) ;
root = Merge(Merge(x , New(w)) , y) ;
}
inline void Del(int &root , LL w) {
int x , y , z ;
Split(root , w , x , z) ;
Split(x , w - 1 , x , y) ;
y = Merge(son[y][0] , son[y][1]) ;
root = Merge(Merge(x , y) , z) ;
}
inline LL Rnk_val(int now , int k) {
while(1) {
if(k <= size[ls]) now = ls ;
else if(k == size[ls] + 1) return val[now] ;
else k -= size[ls] + 1 , now = rs ;
}
}
inline LL Kth_Sum(int now , int k) { // 找前k大元素的和
if(!k) return 0 ; LL ret = 0 ;
while(1) {
if(k <= size[ls]) now = ls ;
else if(k == size[ls] + 1) {
ret += sum[ls] + val[now] ;
return ret ;
}
else {
ret += sum[ls] + val[now] ;
k -= size[ls] + 1 ;
now = rs ;
}
}
}
}
void dfs(int u , int father) {
vis[u] = Tag ; f[u][0] = f[u][1] = 0 ;
if(d[u] <= Tag) return ;
for(int i = 0 , v , w , sz = vec[u].size() ; i < sz ; i ++) {
v = vec[u][i].v , w = vec[u][i].w ;
if(v == father) continue ;
dfs(v , u) ;
f[u][0] += f[v][0] ; f[u][1] += f[v][0] ;
fhq::Insert(rt[u] , f[v][1] + w - f[v][0]) ;
}
int cnt = 0 ; LL x , y , v ;
int l = 1 , r = fhq::size[rt[u]] , ret = 0 , mid ;
while(l <= r) { // 找有几个小于0
mid = (l + r) >> 1 ;
if(fhq::Rnk_val(rt[u] , mid) < 0) ret = mid , l = mid + 1 ;
else r = mid - 1 ;
}
if(ret <= d[u] - Tag)
f[u][0] += fhq::Kth_Sum(rt[u] , d[u] - Tag) ;
else f[u][0] += fhq::Kth_Sum(rt[u] , ret) ;
if(ret <= d[u] - Tag - 1)
f[u][1] += fhq::Kth_Sum(rt[u] , d[u] - Tag - 1) ;
else f[u][1] += fhq::Kth_Sum(rt[u] , ret) ;
for(int i = 0 , v , w , sz = vec[u].size() ; i < sz ; i ++) {
v = vec[u][i].v , w = vec[u][i].w ;
if(v == father) continue ;
fhq::Del(rt[u] , f[v][1] + w - f[v][0]) ;
}
}
int main() {
n = read() ;
for(int i = 1 , u , v , w ; i < n ; i ++) {
u = read() ; v = read() ; w = read() ;
add_edge(u , v , w) ; add_edge(v , u , w) ;
++ d[u] ; ++ d[v] ; ans += w ;
}
fdfs(1 , 0) ;
for(int i = 1 ; i <= n ; i ++) {
pi[i] = i ;
dmx = max( dmx , d[i] ) ;
sort(vec[i].begin() , vec[i].end()) ;
}
sort(pi + 1 , pi + n + 1 , cmp) ;
printf("%lld ",ans) ;
for(int x = 1 , Now = 1 ; x < n ; x ++) {
Tag = x ; ans = 0 ;
while(Now < n && d[pi[Now]] <= x) {
f[pi[Now]][0] = 0 ;
f[pi[Now]][1] = 0 ;
++ Now ;
}
for(int j = Now ; j <= n ; j ++) {
int v ;
while(!vec[pi[j]].empty()) {
v = vec[pi[j]][vec[pi[j]].size() - 1].v ;
if(d[v] <= x) {
if(pi[j] == fa[v])
fhq::Insert( rt[pi[j]] , fdis[v] ) ;
vec[pi[j]].pop_back() ;
}
else break ;
}
}
for(int j = Now , u ; j <= n ; j ++)
if(vis[pi[j]] != x) {
u = pi[j] ;
while(fa[u] && d[fa[u]] > x)
u = fa[u] ;
dfs(u , 0) ;
ans += min(fdis[u] > 0 ? f[u][1] + fdis[u] : INF , f[u][0]) ;
}
printf("%lld ",ans) ;
}
return 0 ;
}