锐客网

  1. 首页 > it技术 > >

牛客练习赛61|牛客练习赛61 苹果树

链接 点击跳转
题解 动态树分治
这个名字虽然看上去貌似挺吓人的，其实原理很简单
就是你点分治的时候不是先找到一个重心 G G G吗，然后你利用这个重心 G G G把树分成了好几块，接下来在每个子树里面再去找重心 g 1 , g 2 , g 3 , … g_1,g_2,g_3,\dots g1?,g2?,g3?,…，那么我令 g 1 , g 2 , g 3 , … g_1,g_2,g_3,\dots g1?,g2?,g3?,…成为 G G G的孩子，这样递归建立一棵树，这个树就被称为点分树
点分树的树高是 O ( l o g n ) O(logn) O(logn)的
点分树用来干啥呢？
可以想一想，我们在做点分治的时候，是不是通过枚举重心就能够遍历到所有的路径？这里我们依然利用重心的这个特性
以某个点 u u u为端点的所有路径怎么遍历呢？很简单，如果一条路径以 u u u为端点，那么这个路径肯定经过点分树中从 u u u到根节点这条链上的某个点。这一点从点分治的过程就可以看出来。
那么这个题怎么做呢？很简单，在点分树的每个点 u u u建立一个以苹果成熟度为下标的线段树，维护从 u u u到其子树（点分树的子树）中每个节点的真实距离的最小值（真实距离=在原来的树上的距离）。
【牛客练习赛61|牛客练习赛61 苹果树】修改的时候沿着点分树往上跳，一边跳一边修改，查询的时候同理。
代码

#include #include #include #define iinf 0x3f3f3f3f #define eps 1e-8 #define maxn 100010 #define maxe 200010 #define maxk 17 #define cl(x) memset(x,0,sizeof(x)) #define rep(i,a,b) for(i=a; i<=b; i++) #define drep(i,a,b) for(i=a; i>=b; i--) #define em(x) emplace(x) #define emb(x) emplace_back(x) #define emf(x) emplace_front(x) #define fi first #define se second #define de(x) cerr<<#x<<" = "<>1); if(!o)o=New(v); else Min[o]=min(Min[o],v); if(l==r)return o; if(pos<=mid)ch[o][0]=insert(ch[o][0],pos,v,l,mid); else ch[o][1]=insert(ch[o][1],pos,v,mid+1,r); return o; } int qmin(int o, int wantl, int wantr, int l, int r) { int mid(l+r>>1), ret=iinf; if(wantl<=l and r<=wantr)return getmin(o); if(wantl<=mid)ret=min(ret,qmin(ch[o][0],wantl,wantr,l,mid)); if(wantr>mid)ret=min(ret,qmin(ch[o][1],wantl,wantr,mid+1,r)); return ret; } }segtree; struct Doubling_LCA { int f[maxn][maxk+1], depth[maxn]; void clear(int n){for(int i=1; i<=n; i++)depth[i]=0, cl(f[i]); } void dfs(Graph &G, int pos, int pre) { for(auto k=1; (1<=depth[y]) x=f[x][k]; if(x==y)return x; for(auto k(maxk); ~k; k--) if(f[x][k]!=f[y][k]) x=f[x][k], y=f[y][k]; return f[x][0]; } int jp(int x, int b) { for(auto k=0; k<=maxk; k++) if(b&(1<

    推荐阅读


    上一篇：Different Integers

    下一篇：javascript|数组求和为指定数字