问题标题: 洛谷：P3038 刚学树剖的萌新求助QAQ

Question

5

陆麟瑞

资深天翼

完了完了，现在连树剖都不会了，NOIP怕是要凉。

WA8个点，37分。

错误代码：

#include <iostream>
using namespace std;
#define it long long
const long long MAXN=1001000;
long long a[MAXN];
long long size[MAXN];
long long head[MAXN];
long long nex[MAXN];
long long to[MAXN];
long long dep[MAXN];
long long son[MAXN];
long long id[MAXN],id2[MAXN];
long long top[MAXN];
long long wt[MAXN],cost[MAXN];
long long father[MAXN];
long long numb[MAXN];
struct xianduan{
    it l,r,sum,sum2;
};
xianduan tree[2000101];
long long tree2[MAXN];
long long tree3[MAXN]; 
long long cnt,mod;
long long num;
void build(it x,it l,it r)
{
    tree[x].l=l;
    tree[x].r=r;
    if(l==r)
    {
        tree[x].sum2=wt[id2[l]];
        return;
    }
    build(x*2,l,(l+r)>>1);
    build(x*2+1,1+((l+r)>>1),r);
    tree[x].sum2=tree[x*2].sum2+tree[x*2+1].sum2;
}
it query1(it x,it l,it r)
{
    if(tree[x].l>=l&&tree[x].r<=r)
        return tree[x].sum2;
    if(tree[x].l>r||tree[x].r<l)
        return 0;
    tree[x].sum2=tree[x*2].sum2+tree[x*2+1].sum2;
    return (query1(x*2,l,r)+query1(x*2+1,l,r)) ;
}
void update(it x,it l,it r,it k)
{
    if(tree[x].l>=l&&tree[x].r<=r)
    {
        tree[x].sum2+=k;
        return;
    }
    if(tree[x].l>r||tree[x].r<l)
        return;
    update(x*2,l,r,k);
    update(x*2+1,l,r,k);
    tree[x].sum2=tree[x*2].sum2+tree[x*2+1].sum2;
}
void add(long long x,long long y,long long z)
{
    nex[++cnt]=head[x];
    cost[cnt]=z;
    to[cnt]=y;
    head[x]=cnt;
    nex[++cnt]=head[y];
    cost[cnt]=z;
    to[cnt]=x;
    head[y]=cnt;
}
void dfs1(long long x,long long f,long long deep)
{
    dep[x]=deep;
    father[x]=f;
    size[x]=1;
    long long maxson=0;
    for(long long i=head[x];i;i=nex[i])
    {
        long long y=to[i];
        if(y==f)continue;
        wt[to[i]]=cost[i];
        numb[i/2]=to[i];
        dfs1(y,x,deep+1);
        size[x]+=size[y]; 
        if(size[y]>maxson) son[x]=y,maxson=size[y];
    }
}
void dfs2(long long x,long long topf)
{ 
    top[x]=topf;
    id[x]=++cnt;
    id2[cnt]=x;
    if(!son[x])return;
    dfs2(son[x],topf);
    for(long long i=head[x];i;i=nex[i]){
        long long y=to[i];
        if(y==father[x]||y==son[x])continue;
        dfs2(y,y);
    }
}
void sp2(long long x,long long y,long long k)
{ 
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(1,id[top[x]],id[x],k);
        x=father[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    update(1,id[y]+1,id[x],k);
}
inline long long sp3(long long x,long long y)
{
    long long ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        num=0;
        num=query1(1,id[top[x]],id[x]);
        ans+=num;
        x=father[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    num=0;
    num=query1(1,id[y]+1,id[x]);
    ans+=num;
    return ans;
}
int main()
{
    long long n,m,s;
    cin>>n>>m;
    s=1;
    cnt++;
    for(long long i=1; i<=n-1; i++)
    {
        long long a,b;
        cin>>a>>b;
        add(a,b,1);
    }
    cnt=0;
    dfs1(s,-1,1); 
    dfs2(s,s);
    build(1,1,n);
    string as;
    while(m--)
    {
        long long x,y,z;
        char a;
        cin>>a;
        if(a=='P')
        {
            cin>>x>>y;
            sp2(x,y,1);
            //a[x]=y;
        }
        else
        {
            cin>>x>>y;
            cout<<sp3(x,y)-1<<endl;
        }
    }
    return 0;
}

@刘孟博

陆麟瑞在2018-10-05 20:55:13追加了内容

刷梗的都是能AKIOI大佬

Answer 1

武宸锐

初级光能

Answer 2

陆麟瑞

资深天翼

刚才手残把“追问”点成了“举报”，结果...

管理大大无视啊QAQ

@梁彦博 @酷町喵~o( =∩ω∩= )o~

Answer 3

赵逸凡

初级启示者

海星什么意思陆巨佬？

@陆麟瑞 @陆麟瑞

我是个不会搜索的蒟蒻，请问树剖跟剪枝有什么关系?

还有下次please您不要说自己“萌新”

赵逸凡在2018-10-13 18:48:54追加了内容

陆巨佬，只是一个小小的询问，并不是针对此问题。 @陆麟瑞 @陆麟瑞 @陆麟瑞

赵逸凡在2018-10-13 18:49:57追加了内容

还有，您觉得您的NOIP能拿多少分，答案发下来了

Answer 4

李致远

高级光能

根据树的性质可以知道，一个点可以有多个儿子，但是只会有一个爸爸,

可以把这个点和它爸爸之间的那条边的边权转移到这个点上来用这个点的点权来表示这条边的权值因为根节点没有爸爸，所以它不表示任何边权，点权为0

在Query或者Modify的时候，都是当x和y同时处于一条链了之后就break

然后再把这条链加上，最近公共祖先不就是这条链的top嘛！

所以，在while循环外边写node[x].s+1就可以不算上公共祖先了。

但是也要注意，如果最后是条轻边，我们就要if特判一下，不能让他进线段树查询了

因为如果是轻边的话，最后的那条链退化成了最近公共祖先这一个点，不能要！

大致思路：

1.读入，连边，树剖。

-

2.对于'P'操作，我们只需在这个路径上的除了公共祖先以外的所有点添加1即可。

可以在草稿纸上随便画上一颗树，每次在边上添加可以转化为添加某条边的底端（即深度大的那个点），显而易见，这样做，一个点是必定对应一条边的。

但LCA那个点不属于我们要查的路径，所以当两个点跳到一条链上时，设x的深度小于y的深度，id[x]为x在树状数组上的编号，那么id[x]（即LCA）不在这条路径上，添加时只添加(id[x]+1,id[y])即可~！

-

3.对于'Q'操作，因为题目说在查询的时候只需要查“一条边”，而不是“一段路径”。所以在树状数组上单点查寻两端点深的那个端点即可（深的那个代表了一条边，如思路2所述）。

Answer 5

朱优扬

中级天翼

1 年，9 月前？？？

Answer 6

柯以成

新手光能

帮陆大佬顶贴

Answer 7

黄子澄

中级天翼

？？？

Answer 8

陈熙熹

资深守护

谁在那里顶这个贴？

Answer 9

潘晨皓

高级天翼

Answer 10

何冯成

中级光能

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int cnt,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1];
int n,Q,t[MAXN<<2],tag[MAXN<<2];
int siz[MAXN],son[MAXN],dfn[MAXN],Index,top[MAXN],dep[MAXN],faz[MAXN];
string s;
void AddEdge(int u,int v)
{
    to[++cnt]=v;
    nxt[cnt]=fst[u];
    fst[u]=cnt;
}
void Dfs1(int u)
{
    siz[u]=1;
    son[u]=0;
    for(int i=fst[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==faz[u]) continue;
        faz[v]=u;
        dep[v]=dep[u]+1;
        Dfs1(v);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v]) son[u]=v;
    }
}
void Dfs2(int u,int rt)
{
    dfn[u]=++Index;
    top[u]=rt;
    if(son[u]) Dfs2(son[u],rt);
    for(int i=fst[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==faz[u] || v==son[u]) continue;
        Dfs2(v,v);
    }
}
void PushUp(int rt)
{
    t[rt]=t[rt<<1]+t[rt<<1|1];
}
void PushDown(int rt)
{
    tag[rt<<1]+=tag[rt];
    tag[rt<<1|1]+=tag[rt];
    t[rt<<1]+=tag[rt];
    t[rt<<1|1]+=tag[rt];
    tag[rt]=0;
}
void BuildSegmentTree(int rt,int l,int r)
{
    if(l==r)
    {
        t[rt]=0;
        return;
    }
    int mid=l+r>>1;
    BuildSegmentTree(rt<<1,l,mid);
    BuildSegmentTree(rt<<1|1,mid+1,r);
    PushUp(rt);
}
void Modify(int rt,int l,int r,int tl,int tr,int val)
{
    if(tl<=l && r<=tr)
    {
        t[rt]+=val;
        tag[rt]+=val;
        return;
    }
    PushDown(rt);
    int mid=l+r>>1;
    if(tl<=mid) Modify(rt<<1,l,mid,tl,tr,val);
    if(tr>mid) Modify(rt<<1|1,mid+1,r,tl,tr,val);
    PushUp(rt);
}
int Query(int rt,int l,int r,int tl,int tr)
{
    if(tl<=l && r<=tr) return t[rt];
    PushDown(rt);
    int mid=l+r>>1,res=0;
    if(tl<=mid) res+=Query(rt<<1,l,mid,tl,tr);
    if(tr>mid) res+=Query(rt<<1|1,mid+1,r,tl,tr);
    return res;
}
void ModifyOnTree(int u,int v,int val)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        Modify(1,1,n,dfn[top[u]],dfn[u],val);
        u=faz[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    Modify(1,1,n,dfn[u]+1,dfn[v],val);
}
int QueryOnTree(int u,int v)
{
    int res=0;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        res=max(res,Query(1,1,n,dfn[top[u]],dfn[u]));
        u=faz[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    res=max(res,Query(1,1,n,dfn[u]+1,dfn[v]));
    return res;
}
int main()
{
    scanf("%d %d",&n,&Q);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d %d",&x,&y);
        AddEdge(x,y);
        AddEdge(y,x);
    }
    Dfs1(1);
    Dfs2(1,1);
    BuildSegmentTree(1,1,n);
    while(Q--)
    {
        int x,y,z;
        cin>>s;
        scanf("%d %d",&x,&y);
        if(s=="P") ModifyOnTree(x,y,1);
        else if(s=="Q") printf("%d\n",QueryOnTree(x,y));
    }
    return 0;
}

Answer 11

徐云皓

新手天翼

http://www.cnblogs.com/1227xq/p/6813288.html

https://blog.csdn.net/JamesKerry/article/details/77647136

https://blog.csdn.net/SindarDawn/article/category/6466990

https://yq.aliyun.com/wenji/245451

Answer 12

邹昊轩

资深光能

大佬牛掰，我们这些渣渣都不会。

Answer 13

汪宇航

新手启示者

......aaa

Answer 14

张弘毅

高级守护

我不知道

Answer 15

汪宇航

新手启示者

......aaa

Answer 16

汪宇航

新手启示者

......aaa

Answer 17

李玥仑

中级光能

你是萌新，我是啥？

Answer 18

武宸锐

初级光能

原来如此

Answer 19

邓涵睿

中级天翼

这题本蒟蒻做不出来

Answer 20

李玥仑

中级光能

为大佬一顶！ヾ(@^▽^@)ノ

Answer 21

王文博

缔造者之神

https://wenda.codingtang.com/questions/12074/

快看

Answer 22

王文博

缔造者之神

太厉害了！！！！

Answer 23

岳成浩

资深守护

Answer 24

赵朗

高级光能

不会

Answer 25

朱睿祥

中级守护

我是大佬!

Answer 26

杨弘毅

中级光能

ding

Answer 27

周俊豪

高级光能

dalao你代码太长了，我们蒟蒻做不到啊。。。。。。

Answer 28

胡家翊

高级守护

。。。。。我流下了蒟蒻的眼泪

Answer 29

陈俊霖

资深光能

树链剖分！我**！我作为一个打比赛没有下过市级第20，省级第50的我感到一个face的懵**

Answer 30

陶旭杰

中级光能

弱弱的问一句：树剖是啥？

问题标题: 洛谷：P3038 刚学树剖的萌新求助QAQ

30 个回答: