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

5
2
陆麟瑞
陆麟瑞
资深天翼
资深天翼

完了完了，现在连树剖都不会了，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大佬

举报

10酷町豆 刷题求解 6条评论 6 年，1 月 前

4
2
陆麟瑞
陆麟瑞
资深天翼
资深天翼

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

管理大大无视啊QAQ

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

阅读更多
举报

6 年，1 月 前 3条评论

1
赵逸凡
赵逸凡
初级启示者
初级启示者

海星什么意思陆巨佬？

@陆麟瑞 @陆麟瑞 

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

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

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

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

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

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

 

 

 

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

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

阅读更多
举报

6 年，1 月 前 2条评论

1
李致远
李致远
高级光能
高级光能

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

可以把这个点和它爸爸之间的那条边的边权转移到这个点上来用这个点的点权来表示这条边的权值因为根节点没有爸爸，所以它不表示任何边权，点权为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所述）。

阅读更多
举报

4 年，7 月 前 2条评论

0
朱优扬
朱优扬
中级天翼
中级天翼

 1 年，9 月 前？？？

阅读更多
举报

4 年，3 月 前 2条评论

0
0
0
0
0
被禁言 何冯成
何冯成
中级光能
中级光能 
#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;
}

 

阅读更多
举报

4 年，9 月 前 3条评论

0
0
邹昊轩
邹昊轩
资深光能
资深光能

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

阅读更多
举报

4 年，7 月 前 1条评论

0
0
0
0
0
0
0
0
李玥仑
李玥仑
中级光能
中级光能

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

阅读更多
举报

3 年，6 月 前 2条评论

0
0
0
0
0
0
0
周俊豪
周俊豪
高级光能
高级光能

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

阅读更多
举报

6 年，1 月 前 0条评论

0
胡家翊
胡家翊
高级守护
高级守护

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

阅读更多
举报

4 年，4 月 前 2条评论

0
陈俊霖
陈俊霖
新手天翼
新手天翼

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

阅读更多
举报

2 年，1 月 前 3条评论

0
陶旭杰
陶旭杰
中级光能
中级光能

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

阅读更多
举报

4 年，4 月 前 2条评论

我要回答
© 2021 酷町堂教育机构 版权所有 皖ICP备16015773号-1