请选择 进入手机版 | 继续访问电脑版

阔力梯的树(树上启发式合并+set)

[复制链接]
二次方先生 发表于 2021-1-3 12:15:48 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
传送门
人都傻了
                               d                      s                      u                          dsu               dsu倒是模板,被                              s                      e                      t                          set               set的操纵搞晕了…
                               s                      .                      l                      o                      w                      e                      r                      _                      b                      o                      u                      n                      d                      (                      i                      n                      t                      )                          s.lower\_bound(int)               s.lower_bound(int)返回一个大于即是查找元素的指针
                               s                      .                      e                      n                      d                      (                      )                          s.end()               s.end()是                              s                      e                      t                          set               set的末端位置,但是最后一个元素在末端位置的前面                              !                      !                      !                          !!!               !!!
当                              l                      o                      w                      e                      r                      _                      b                      o                      u                      n                      d                          lower\_bound               lower_bound返回                              s                      .                      e                      n                      d                      (                      )                          s.end()               s.end()说明没找到这个元素
至于这里用                              s                      e                      t                          set               set也是有原因的,因为编号不重复,否则需要使用                              m                      u                      l                      t                      i                      s                      e                      t                          multiset               multiset
  回到这道题,维护每个点的坚固度
显然想知道一个点的坚固度必须要把所有子节点的编号排成一个序列盘算
但是直接盘算是                              O                      (                               n                         2                              )                          O(n^2)               O(n2)的
思量到这个序列是可以归并的,答案也是小幅度修改,可以使用                              d                      s                      u                          dsu               dsu
使用                              s                      e                      t                          set               set来储存当前子树内的编号序列
加入一个编号时,直接                              l                      o                      w                      e                      r                      _                      b                      o                      u                      n                      d                          lower\_bound               lower_bound找到插入的前驱后继,累加权值
删除时同理
这样就变成模板了
插入时分四种情况来写
                               s                      e                      t                          set               set内元素个数只有                              1                          1               1个
无前驱
无后继
有前驱和后继
删除同理
然后就直接套用                              d                      s                      u                      _                      o                      n                      _                      t                      r                      e                      e                          dsu\_on\_tree               dsu_on_tree的模板
[code]#include using namespace std;#define int long longconst int maxn = 2e5+10;struct edge{        int to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v){ d[++cnt] = (edge){v,head},head = cnt; }int n,m,son[maxn],siz[maxn],sum,SON,ans[maxn];void dfs(int u){        siz = 1;        for(int i=head;i;i=d.nxt )        {                int v = d.to;                dfs(v);                siz += siz[v];                if( siz[v]>siz[son] )        son = v;        }}sets;set::iterator it;int pre(set::iterator it)        { return *(--it); }int nxt(set::iterator it)        { return *(++it); }void ADD(int u){        if( !s.size() )        { s.insert(u); return; }        it = s.lower_bound(u);//找到第一个大于即是的        int pr = pre(it), nx = *it;        if( it==s.begin() )        sum += (nx-u)*(nx-u);        else if( it==s.end() )        sum += (u-pr)*(u-pr);        else        {                sum -= (nx-pr)*(nx-pr);                sum += (nx-u)*(nx-u)+(u-pr)*(u-pr);        }        s.insert(u);}void del(int u){        if( s.size()==1 )        { s.erase(u); return; }        it = s.lower_bound(u);        int pr = pre(it),nx = nxt(it);        if( it==s.begin() )        sum -= (nx-*it)*(nx-*it);        else if( *it==pre(s.end()) )        sum -= (pr-*it)*(pr-*it);        else        {                sum += (nx-pr)*(nx-pr);                sum -= (nx-u)*(nx-u)+(u-pr)*(u-pr);        }        s.erase(u);}void cal(int u,int type){        ( type?ADD(u):del(u) );         for(int i=head;i;i=d.nxt )        {                int v = d.to;                if( v!=SON )        cal( v,type );        }}void dsu(int u,int type){        for(int i=head;i;i=d.nxt )        {                int v = d.to;                if( v!=son )        dsu( v,0 );        }        if( son )        dsu( son,1 ),SON = son;        cal(u,1); ans = sum; SON=0;        if( !type )        cal(u,0);}signed main(){        cin >> n;        for(int i=2;i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )