树剖经验总结——边权转点权的注意事项

张钧皓 · 2018-02-28 19:20:46 · 个人记录

P3950 部落冲突
因为一个细节被卡了一个半小时。
让我更迷惑的是以不同的点为根建树竟然 A 掉的点不一样。
组里大佬两分钟找出问题，感觉智商被暴踩。
主要问题是这样的：
题目要求是边修改，于是我自以为是地把边修改转为对深度较深点的点修改。
一试样例竟然过了，心想没什么毛病了。
但是问题来了：
在查询时，两点的 LCA 的权值也被计算了。
但注意了，以我的思路， LCA 的状态其实是其父边的状态，它对答案不应有影响！
由此可见在将边权推为点权时，一定要考虑 LCA 的影响。

修改其实非常简单。
因为树剖查询时，最后当两点在同一重链上时，深度低的点事实上就是 LCA 。
只要忽略掉它的影响就可以了。
上代码：

#include<iostream>
#include<cstdio>
#define ll long long
#define M 300005
#define N 600005
using namespace std;
//-------------------------------------------------------------
ll read()
{
    ll data=0,w=1;
    char c=getchar();
    while(c!='-'&&(c<'0'||c>'9'))
        c=getchar();
    if(c=='-')
        w=-1,c=getchar();
    while(c>='0'&&c<='9')
        data=data*10+c-'0',c=getchar();
    return data*w;
}
//-------------------------------------------------------------
struct edge
{
    ll to,next;
} e[N];
ll head[M],cnt=0;
void adde(ll x,ll y)
{
    cnt++;
    e[cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt;
}
//-------------------------------------------------------------
ll n,m;
ll size[M],daddy[M],son[M],dfn[M],dep[M],top[M];
//-------------------------------------------------------------
void dfs1(ll x,ll f,ll deep)
{
    daddy[x]=f;
    dep[x]=deep;
    size[x]=1;
    ll mason=-1,v;
    for(ll u=head[x];u;u=e[u].next)
    {
        v=e[u].to;
        if(v==f)
            continue;
        dfs1(v,x,deep+1);
        size[x]+=size[v];
        if(size[v]>mason)
            mason=size[v],son[x]=v;
    }
}
//-------------------------------------------------------------
ll cmt=0;
void dfs2(ll x,ll t)
{
    dfn[x]=++cmt;
    top[x]=t;
    ll v;
    if(!son[x])
        return ;
    dfs2(son[x],t);
    for(ll u=head[x];u;u=e[u].next)
    {
        v=e[u].to;
        if(v==daddy[x]||v==son[x])
            continue ;
        dfs2(v,v);
    }
}
//-------------------------------------------------------------
ll tre[M],a[M];
ll lowbit(ll x)
{
    return (x&(-x));
}
ll gap(ll x)
{
    ll s=0;
    for(ll i=x;i>=1;i-=lowbit(i))
        s+=tre[i];
    return s;
}
ll dow(ll x)
{
    for(ll i=x;i<=n;i+=lowbit(i))
        tre[i]-=1;
}
ll upo(ll x)
{
    for(ll i=x;i<=n;i+=lowbit(i))
        tre[i]+=1;
}
//-------------------------------------------------------------
bool qran(ll x,ll y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        if((gap(dfn[x])-gap(dfn[top[x]]-1))<0)
            return 1;
        x=daddy[top[x]];
    }
    if(dep[x]<dep[y])
        swap(x,y);
    if(gap(dfn[x])-gap(dfn[y])<0)//就是这里
        return 1;          //原本是dfn[y]-1
    return 0;
}
//-------------------------------------------------------------
ll war[M],o=0;
int main()
{
    cin>>n>>m;
    ll u,v;
    for(ll i=1;i<n;i++)
    {
        u=read();
        v=read();
        adde(u,v);
        adde(v,u);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    for(ll i=1;i<=n;i++)
        tre[i]=0;
    char la;
    for(ll i=1;i<=m;i++)
    {
        cin>>la;
        if(la=='Q')
        {
            u=read();
            v=read();
            if(qran(u,v)==1)
                cout<<"No"<<endl;
            else
                cout<<"Yes"<<endl;
        }
        if(la=='C')
        {
            u=read();
            v=read();
            if(dep[u]<dep[v])
                swap(u,v);
            dow(dfn[u]);
            war[++o]=u;
        }
        if(la=='U')
        {
            u=read();
            upo(dfn[war[u]]);
        }
    }
}