首页 > 其他分享 >SP14943 DRTREE - Dynamically-Rooted Tree 题解

SP14943 DRTREE - Dynamically-Rooted Tree 题解

时间:2024-05-26 11:22:00浏览次数:35  
标签:rt DRTREE Rooted dep 题解 ll 200010 return top

题目传送门

前置知识

树链剖分 | 线段树

解法

树剖换根,子树查询板子。

类似 换根 DP 的思路,我们发现换根后仅有祖先、子树、深度等会随祖先的变化而变化。

设 \(rt_{i}\) 表示第 \(i\) 次操作的树根,\(x_{i}\) 表示第 \(i\) 次操作的节点。接着进行大力分讨。

  • 当 \(rt_{i}=x_{i}\) 时,等价于查询整棵树。
  • 当 \(rt_{i} \ne x_{i}\) 且 \(rt_{i}\) 不在以 \(1\) 为根时以 \(x_{i}\) 为根的子树内,换根对其没有影响,等价于查询以 \(1\) 为根时以 \(x\) 为根的子树。
  • 当 \(rt_{i} \ne x_{i}\) 且 \(rt_{i}\) 在以 \(1\) 为根时以 \(x_{i}\) 为根的子树内,换根对其产生影响,等价于查询整棵树除了以 \(1\) 为根时以 \(x\) 为根的子树中 \(rt_{i}\) 所在的方向的子树。可以分别求出后相减,也可以拆成两段区间求和。
    • 现在问题成了如何求一个 \(y\) 使得 \(\begin{cases} y \in Son(x) \\ rt_{i} \in Subtree(y) \end{cases}\)。
      • 对于节点 \(x,rt_{i}\) 不断向上跳重链,若不在同一条重链上时就已经满足条件则直接返回;否则,当跳到同一条重链上时,深度较小的节点的重儿子即为 \(y\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
struct node
{
    ll nxt,to;
}e[200010];
ll head[200010],c[200010],cc[200010],siz[200010],fa[200010],dep[200010],son[200010],top[200010],dfn[200010],out[200010],cnt=0,tot=0;
struct SegmentTree
{
    ll l,r,sum;
}tree[800010];
ll lson(ll x)
{
    return x*2;
}
ll rson(ll x)
{
    return x*2+1;
}
void pushup(ll rt)
{
    tree[rt].sum=tree[lson(rt)].sum+tree[rson(rt)].sum;
}
void build(ll rt,ll l,ll r)
{
    tree[rt].l=l;
    tree[rt].r=r;
    if(l==r)
    {
        tree[rt].sum=cc[l];
        return;
    }
    ll mid=(l+r)/2;
    build(lson(rt),l,mid);
    build(rson(rt),mid+1,r);
    pushup(rt);
}
ll query(ll rt,ll x,ll y)
{
    if(x<=tree[rt].l&&tree[rt].r<=y)
    {
        return tree[rt].sum;
    }
    ll mid=(tree[rt].l+tree[rt].r)/2,ans=0;
    if(x<=mid)
    {
        ans+=query(lson(rt),x,y);
    }
    if(y>mid)
    {
        ans+=query(rson(rt),x,y);
    }
    return ans;
}
void add(ll u,ll v)
{
    cnt++;
    e[cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
void dfs1(ll x,ll father)
{
    siz[x]=1;
    fa[x]=father;
    dep[x]=dep[father]+1;
    for(ll i=head[x];i!=0;i=e[i].nxt)
    {
        if(e[i].to!=father)
        {
            dfs1(e[i].to,x);
            siz[x]+=siz[e[i].to];
            son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x];
        }
    }
}
void dfs2(ll x,ll father,ll id)
{
    top[x]=id;
    tot++;
    dfn[x]=tot;
    cc[tot]=c[x];
    if(son[x]!=0)
    {        
        dfs2(son[x],x,id);
        for(ll i=head[x];i!=0;i=e[i].nxt)
        {
            if(e[i].to!=father&&e[i].to!=son[x])
            {
                dfs2(e[i].to,x,e[i].to);
            }
        }
    }
    out[x]=tot;
}
ll dirson(ll u,ll v)
{
    if(dep[u]>dep[v])
    {
        swap(u,v);
    }
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>dep[top[v]])
        {
            if(fa[top[u]]==v)
            {
                return top[u];
            }
            u=fa[top[u]];
        }
        else
        {
            if(fa[top[v]]==u)
            {
                return top[v];
            }
            v=fa[top[v]];
        }
    }
    return (dep[u]<dep[v])?son[u]:son[v];
}
ll query1(ll pos)
{
    return query(1,dfn[pos],out[pos]);
}
ll query_reroot1(ll x,ll rt)
{
    if(x==rt)
    {
        return query1(1);
    }
    else
    {
        if(dfn[x]<=dfn[rt]&&dfn[rt]<=out[x])
        {
            return query1(1)-query1(dirson(x,rt));
        }
        else
        {
            return query1(x);
        }
    }
}
int main()
{
    ll n,m,u,v,rt=1,i;
    char pd;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>c[i];
    }
    for(i=2;i<=n;i++)
    {
        cin>>u;
        v=i;
        add(u,v);
        add(v,u);
    }
    dfs1(1,0);
    dfs2(1,0,1);
    build(1,1,n);
    cin>>m;
    for(i=1;i<=m;i++)
    {
        cin>>pd;
        if(pd=='S')
        {
            cin>>u;
            cout<<query_reroot1(u,rt)<<endl;
        }
        else
        {
            cin>>rt;
        }
    }
    return 0;
}

标签:rt,DRTREE,Rooted,dep,题解,ll,200010,return,top
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18213443

相关文章

  • 图的dfs遍历题解
    本蒟蒻又来做题啦!看看今天做啥题。。。。题目描述时间:1s 空间:256M题目描述:给出一个无向图和一个起点s,输出这个图从s结点开始的DFS遍历序列。规定:节点邻居按照输入的顺序遍历输入格式:共M+1行。第11行包含33个正整数N,M,s,表示有N个点,M条边,起点为s。第2~M+1行包含2个用......
  • 【题解】 [USACO 2009 Mar] Cow Frisbee Team S
    题目描述题意分析从\(N\)个整数中取若干个(不能不选),且取的数之和为\(F\)的倍数的总方案数对\(10^8\)取余的值。思路这道题是一道二维线性DP。那么根据线性DP的解题方法。首先,找出题目的阶段性。这道题显而易见方案数随着选择的个数而变化,那么这道题就以选择的个数作为阶段......
  • 【赛题解析】【网络建设与运维】2023年全国职业院校技能大赛中职组“网络建设与运维”
    在此之前,欢迎关注波比网络波比网络官方公众号:blbinet波比网络工作室官方公众号:blbistudio技能大赛各赛项交流群:https://www.blbi.cn/threads/40/更多正式赛题源文件访问:https://www.blbi.cn获取技术支持访问:https://www.blbi.cn/form/1/selectNISP、CIPS、PTE证书可......
  • 【赛题解析】【网络建设与运维】2023年全国职业院校技能大赛中职组“网络建设与运维”
    在此之前,欢迎关注波比网络波比网络官方公众号:blbinet波比网络工作室官方公众号:blbistudio技能大赛各赛项交流群:https://www.blbi.cn/threads/40/更多正式赛题源文件访问:https://www.blbi.cn获取技术支持访问:https://www.blbi.cn/form/1/selectNISP、CIPS、PTE证书可......
  • Tokio Marine & Nichido Fire Insurance Programming Contest 2024(AtCoder Beginner C
    A-WhoAtetheCake?题意:有三个嫌疑犯(1,2,3(号码))现在有两个证人他们指出谁不是嫌疑犯,你可以找到确定的那个罪人吗?找到输出这个人的号码没找到输出-1思路:如果两人指出的人是一个人则输出-1不是则输出6-a-b,因为1+2+3=6(sum)减去a,b肯定可以到达......
  • 题解:P8267 [USACO22OPEN] Counting Liars B & U208878 晴天
    其实,这个题,只需要最简单的枚举,加上最简单的二分查找即可~\(1\leN\le1000\)?枚举吧~咋枚举?显然,最好状态下Bessie的位置一定是某个\(p_i\),否则差一个就会导致有个奶牛要说谎。所以我们枚举(理论来讲要先去个重,这样快一点,不过貌似数据没有重的~)\(p_i\),每次遍历这帮奶牛看看有......
  • 2024XJTUPC西安交通大学校赛VP题解
    每次vp都自闭,已成习惯,时间还是分配的不合理,debug时做太多无用功。一键做题A.交小西的礼物输出a+b+2c+3d即可#pragmaGCCoptimize(3,"Ofast","inline")#include<bits/stdc++.h>#defineinf0x3f3f3f3f3fusingnamespacestd;usingll=longlong;usingpii=......
  • 题解【[SCOI2008] 配对】
    题目链接如果没有“配对数字不相同”的限制,将\(a,b\)数组排序后一一配对就能得到最小值。回到原题,考虑一种极端情况,\(\foralli\in[1,n],a_i=b_i\)即排序后全等。若\(n\)为偶数,一种显然的构造方法是:123456214365即分成两个两个一组,然后组内交换,这样跨越幅......
  • Xfce4桌面背景和桌面图标消失问题解决@FreeBSD
    问题:Xfce4桌面背景和桌面图标消失以前碰到过好几次桌面背景和桌面图标消失,整个桌面除了上面一条和下面中间的工具条,其它地方全是黑色的问题,但是这次重启之后也没有修复,整个桌面乌黑一片,啥都没有,用起来特别不得劲,于是开始修复。修复过程咨询文心,建议这样设置:检查壁纸设置:......
  • 【NOI2010】能量采集 题解
    【NOI2010】能量采集题解谨纪念我的第一道手推出来的莫反题。题目大意:已知\(n\),\(m\),求\(\sum\limits_{i=1}^n\sum\limits_{j=1}^m(2\cdot\gcd(i,j)-1)\)。首先变形一手:\[\sum\limits_{i=1}^n\sum\limits_{j=1}^m(2\cdot\gcd(i,j)-1)=2\sum\limits_{i=1}^n\sum\limits_{j=......