[ZJOI2015] 地震后的幻想乡
前言
点分树练习题。
题目
洛谷
LOJ
讲解
我们发现这道题相当于找树上带权重心。
有一个我认为挺nb的贪心是从根开始走，每次走最优的那个儿子，走不动了就是答案，而且对于每个当前点，至多只会有一个儿子比它优。
只考虑走的话，复杂度是 \(O(depth)\) 的，考虑优化它，理所当然会想到点分树，再结合每个点度数不超过 20 这个条件，做法基本就明晰了。
从点分树的根开始，在原树上找最优的儿子，走点分树上的边。
现在问题是怎么算花费，其实我们每次修改的时候在点分树上改，查询也可以在点分树上查，记录到点分树上的点的父亲的花费，把这个花费在父亲和该点都记录一下，就可以实现 \(O(\log_2n)\) 查询花费了。当然也需要记录点分树子树的权值和。
为了保证复杂度需要 \(O(1)\) LCA，总复杂度是 \(O(20n\log_2^2n)\)。
代码
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 200005;
int n,Q;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int hd[MAXN],head[MAXN],tot;
struct edge{
int v,w,nxt;
}e[MAXN<<2];
void Add_Edge(int u,int v,int w){
e[++tot] = edge{v,w,head[u]};
head[u] = tot;
}
void Add_Double_Edge(int u,int v,int w){
Add_Edge(u,v,w);
Add_Edge(v,u,w);
}
int dfn[MAXN],dfntot,st[MAXN][19],d[MAXN],who[MAXN],LG[MAXN];
int up(int u,int v){return d[u] < d[v] ? u : v;}
int lca(int u,int v){
u = who[u]; v = who[v];
if(u > v) swap(u,v);
int k = LG[v-u+1];
return up(st[u][k],st[v-(1<>1] + 1;
for(int i = dfntot;i >= 1;-- i)
for(int j = 1;i+(1< 0){
int x = Read(),val = Read(); sd[x] += val;
for(int i = x,dd; i ;i = f[i]){
dd = dis(f[i],x);
dis1[f[i]] += 1ll * dd * val;
dis2[i] += 1ll * dd * val;
sd[f[i]] += val;
}
Put(Query(RT),'\n');
}
return 0;
}
/*
点分
思考怎么修改，爬点分树，乱改
似乎我只需要在点分树里面改贡献就好了
*/