為什麼出錯了?(已解決)

此處的數據能通過(樣例更不用問了):
https://vijos.org/discuss/598482f9d3d8a17a62bbde2d#1603289438
Wrong Answer
/in/foo.cc: In function 'void dts::tr_dfs1(int, int, int)':
/in/foo.cc:28:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<tr[now].s.size();i++)
~^~~~~~~~~~~~~~~~~
/in/foo.cc: In function 'void dts::tr_dfs2(int, int)':
/in/foo.cc:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<tr[now].s.size();i++)
~^~~~~~~~~~~~~~~~~

狀態 耗時 記憶體佔用

#1 Wrong Answer 15ms 26.801 MiB
#2 Wrong Answer 16ms 26.789 MiB
#3 Wrong Answer 15ms 27.148 MiB
#4 Wrong Answer 268ms 30.406 MiB
#5 Wrong Answer 267ms 30.305 MiB
#6 Wrong Answer 266ms 30.41 MiB
#7 Wrong Answer 263ms 30.371 MiB
#8 Wrong Answer 405ms 34.035 MiB
#9 Wrong Answer 402ms 34.023 MiB
#10 Wrong Answer 364ms 33.969 MiB

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
using namespace std;

namespace dts
{
    int ft=1,cnt;
    class tree_node
    {
        public:
            int fa,dep,size,hs,top,id;
            vector<int> s;
    };
    int rk[(1<<17)+1];
    tree_node tr[(1<<17)+1];
    void tr_dfs1(int now,int fa,int dep)
    {
        tr[now].fa=fa;
        tr[now].dep=dep;
        tr[now].size=1;
        tr[now].hs=-1;
        for (int i=0;i<tr[now].s.size();i++)
            if (tr[now].s[i]!=fa)
            {
                int next=tr[now].s[i];
                tr_dfs1(next,now,dep+1);
                tr[now].size+=tr[next].size;
                if (tr[now].hs==-1)
                    tr[now].hs=next;
                else if (tr[tr[now].hs].size<tr[next].size)
                    tr[now].hs=next;
            }
    }
    void tr_dfs2(int now,int top)
    {
        tr[now].top=top;
        tr[now].id=++cnt;
        rk[cnt]=now;
        if (tr[now].hs!=-1)
        {
            tr_dfs2(tr[now].hs,top);
            for (int i=0;i<tr[now].s.size();i++)
                if (tr[now].s[i]!=tr[now].fa&&tr[now].s[i]!=tr[now].hs)
                    tr_dfs2(tr[now].s[i],tr[now].s[i]);
        }
    }
    void tr_build()
    {
        cnt=0;
        tr_dfs1(ft,ft,1);
        tr_dfs2(ft,ft);
    }
    int lca(int x,int y)
    {
        while (tr[x].top!=tr[y].top)
        {
            if (tr[tr[x].top].dep<tr[tr[y].top].dep)
                swap(x,y);
            x=tr[tr[x].top].fa;
        }
        if (tr[x].dep<tr[y].dep)
            return x;
        else
            return y;
    }
    
    class st_node
    {
        public:
            int l,r,mid,empt=1;
            int lans=0,rans=0,ans=0,sum=0;
            int iflz=0,numlz;
            int len()
            {
                return tr[r].dep-tr[l].dep+1;
            }
    };
    int data[(1<<17)+1];
    st_node st[(1<<19)+2];
    #define lc(now) ((now)<<1)
    #define rc(now) ((now)<<1|1)
    st_node merge(st_node li,st_node ri)//li:左子區間,ri:右子區間
    {
        if (li.empt)
            return ri;
        else if (ri.empt)
            return li;
        st_node a;
        a.empt=a.iflz=0;
        a.l=li.l,a.r=ri.r,a.mid=li.r;
        a.lans=max(li.lans,li.sum+ri.lans);
        a.rans=max(ri.rans,ri.sum+li.rans);
        a.ans=max(max(li.ans,ri.ans),li.rans+ri.lans);
        a.sum=li.sum+ri.sum;
        return a;
    }
    void st_pushup(int now)
    {
        st[now]=merge(st[lc(now)],st[rc(now)]);//別在意時間複雜度常數
    }
    void st_update(int now,int l,int r,int val);
    void st_pushdown(int now)
    {
        if (st[now].iflz)
        {
            st_update(lc(now),st[now].l,st[now].mid,st[now].numlz);
            st_update(rc(now),st[now].mid+1,st[now].r,st[now].numlz);
            st[now].iflz=0;
        }
    }
    void st_update(int now,int l,int r,int val)
    {
        if (st[now].l==l&&r==st[now].r)
        {
            st[now].lans=st[now].rans=st[now].ans=max(st[now].len()*val,0);
            st[now].sum=st[now].len()*val;
            st[now].iflz=1,st[now].numlz=val;
        }
        else
        {
            st_pushdown(now);
            if (r<=st[now].mid)
                st_update(lc(now),l,r,val);
            else if (st[now].mid+1<=l)
                st_update(rc(now),l,r,val);
            else
                st_update(lc(now),l,st[now].mid,val),st_update(rc(now),st[now].mid+1,r,val);
            st_pushup(now);
        }
    }
    st_node st_ask(int now,int l,int r)
    {
        if (st[now].l==l&&r==st[now].r)
            return st[now];
        else
        {
            st_pushdown(now);
            if (r<=st[now].mid)
                return st_ask(lc(now),l,r);
            else if (st[now].mid+1<=l)
                return st_ask(rc(now),l,r);
            else
                return merge(st_ask(lc(now),l,st[now].mid),st_ask(rc(now),st[now].mid+1,r));
        }
    }
    void st_build(int now,int l,int r)
    {
        st[now].empt=st[now].iflz=0;
        st[now].l=l,st[now].r=r;
        if (l<r)
        {
            st[now].mid=(l+r)>>1;
            st_build(lc(now),l,st[now].mid);
            st_build(rc(now),st[now].mid+1,r);
            st_pushup(now);
        }
        else
        {
            st[now].sum=data[rk[l]];
            st[now].lans=st[now].rans=st[now].ans=max(data[rk[l]],0);
        }
    }
    
    void update(int x,int y,int val)
    {
        int i,j,lcan=lca(x,y);
        for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
            st_update(1,tr[tr[i].top].id,tr[i].id,val);
        for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
            st_update(1,tr[tr[j].top].id,tr[j].id,val);
        if (tr[i].dep>tr[j].dep)
            swap(i,j);
        st_update(1,tr[i].id,tr[j].id,val);
    }
    st_node cty(st_node stn)
    {
        swap(stn.l,stn.r);
        swap(stn.lans,stn.rans);
        return stn;
    }
    int ask(int x,int y)
    {
        int i,j,lcan=lca(x,y);
        st_node ians,jans,ans;
        ians.iflz=jans.iflz=0;
        ians.empt=jans.empt=1;
        for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
            ians=merge(st_ask(1,tr[tr[i].top].id,tr[i].id),ians);
        for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
            jans=merge(st_ask(1,tr[tr[j].top].id,tr[j].id),jans);
        if (tr[i].dep>tr[j].dep)
            swap(i,j),swap(ians,jans);
        jans=merge(st_ask(1,tr[i].id,tr[j].id),jans);
        ans=merge(cty(jans),ians);
        return ans.ans;
    }
    
    int n,m;
    
    void main()
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%d",&data[i]);
        for (int i=1;i<=n;i++)
            tr[i].s.clear();
        for (int i=1;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            tr[x].s.push_back(y);
            tr[y].s.push_back(x);
        }
        if (n>0)
            tr_build();
        st_build(1,1,cnt);
        scanf("%d",&m);
        for (int i=1;i<=m;i++)
        {
            int K,x,y;
            scanf("%d%d%d",&K,&x,&y);
            if (K==1)
                printf("%d ",ask(x,y));
            else if (K==2)
            {
                int val;
                scanf("%d",&val);
                update(x,y,val);
            }
        }
        printf("\n");
    }
}

int main()
{
    dts::main();
}

3 条评论

  • @ 2020-10-23 01:10:51

    找出問題了:
    正確方式:

        class st_node
        {
            public:
                int l,r,mid,empt=1;
                int lans=0,rans=0,ans=0,sum=0;
                int iflz=0,numlz;
                int len()
                {
                    return tr[rk[r]].dep-tr[rk[l]].dep+1;
                }
        };
    

    完整代碼:

    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <limits>
    using namespace std;
    
    namespace dts
    {
        int ft=1,cnt;
        class tree_node
        {
            public:
                int fa,dep,size,hs,top,id;
                vector<int> s;
        };
        int rk[(1<<17)+1];
        tree_node tr[(1<<17)+1];
        void tr_dfs1(int now,int fa,int dep)
        {
            tr[now].fa=fa;
            tr[now].dep=dep;
            tr[now].size=1;
            tr[now].hs=-1;
            for (int i=0;i<tr[now].s.size();i++)
                if (tr[now].s[i]!=fa)
                {
                    int next=tr[now].s[i];
                    tr_dfs1(next,now,dep+1);
                    tr[now].size+=tr[next].size;
                    if (tr[now].hs==-1)
                        tr[now].hs=next;
                    else if (tr[tr[now].hs].size<tr[next].size)
                        tr[now].hs=next;
                }
        }
        void tr_dfs2(int now,int top)
        {
            tr[now].top=top;
            tr[now].id=++cnt;
            rk[cnt]=now;
            if (tr[now].hs!=-1)
            {
                tr_dfs2(tr[now].hs,top);
                for (int i=0;i<tr[now].s.size();i++)
                    if (tr[now].s[i]!=tr[now].fa&&tr[now].s[i]!=tr[now].hs)
                        tr_dfs2(tr[now].s[i],tr[now].s[i]);
            }
        }
        void tr_build()
        {
            cnt=0;
            tr_dfs1(ft,ft,1);
            tr_dfs2(ft,ft);
        }
        int lca(int x,int y)
        {
            while (tr[x].top!=tr[y].top)
            {
                if (tr[tr[x].top].dep<tr[tr[y].top].dep)
                    swap(x,y);
                x=tr[tr[x].top].fa;
            }
            if (tr[x].dep<tr[y].dep)
                return x;
            else
                return y;
        }
        
        class st_node
        {
            public:
                int l,r,mid,empt=1;
                int lans=0,rans=0,ans=0,sum=0;
                int iflz=0,numlz;
                int len()
                {
                    return tr[rk[r]].dep-tr[rk[l]].dep+1;
                }
        };
        int data[(1<<17)+1];
        st_node st[(1<<19)+2];
        #define lc(now) ((now)<<1)
        #define rc(now) ((now)<<1|1)
        st_node merge(st_node li,st_node ri)//li:左子區間,ri:右子區間
        {
            if (li.empt)
                return ri;
            else if (ri.empt)
                return li;
            st_node a;
            a.empt=a.iflz=0;
            a.l=li.l,a.r=ri.r,a.mid=li.r;
            a.lans=max(li.lans,li.sum+ri.lans);
            a.rans=max(ri.rans,ri.sum+li.rans);
            a.ans=max(max(li.ans,ri.ans),li.rans+ri.lans);
            a.sum=li.sum+ri.sum;
            return a;
        }
        void st_pushup(int now)
        {
            st[now]=merge(st[lc(now)],st[rc(now)]);//別在意時間複雜度常數
        }
        void st_update(int now,int l,int r,int val);
        void st_pushdown(int now)
        {
            if (st[now].iflz)
            {
                st_update(lc(now),st[now].l,st[now].mid,st[now].numlz);
                st_update(rc(now),st[now].mid+1,st[now].r,st[now].numlz);
                st[now].iflz=0;
            }
        }
        void st_update(int now,int l,int r,int val)
        {
            if (st[now].l==l&&r==st[now].r)
            {
                st[now].lans=st[now].rans=st[now].ans=max(st[now].len()*val,0);
                st[now].sum=st[now].len()*val;
                st[now].iflz=1,st[now].numlz=val;
            }
            else
            {
                st_pushdown(now);
                if (r<=st[now].mid)
                    st_update(lc(now),l,r,val);
                else if (st[now].mid+1<=l)
                    st_update(rc(now),l,r,val);
                else
                    st_update(lc(now),l,st[now].mid,val),st_update(rc(now),st[now].mid+1,r,val);
                st_pushup(now);
            }
        }
        st_node st_ask(int now,int l,int r)
        {
            if (st[now].l==l&&r==st[now].r)
                return st[now];
            else
            {
                st_pushdown(now);
                if (r<=st[now].mid)
                    return st_ask(lc(now),l,r);
                else if (st[now].mid+1<=l)
                    return st_ask(rc(now),l,r);
                else
                    return merge(st_ask(lc(now),l,st[now].mid),st_ask(rc(now),st[now].mid+1,r));
            }
        }
        void st_build(int now,int l,int r)
        {
            st[now].empt=st[now].iflz=0;
            st[now].l=l,st[now].r=r;
            if (l<r)
            {
                st[now].mid=(l+r)>>1;
                st_build(lc(now),l,st[now].mid);
                st_build(rc(now),st[now].mid+1,r);
                st_pushup(now);
            }
            else
            {
                st[now].sum=data[rk[l]];
                st[now].lans=st[now].rans=st[now].ans=max(data[rk[l]],0);
            }
        }
        
        void update(int x,int y,int val)
        {
            int i,j,lcan=lca(x,y);
            for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
                st_update(1,tr[tr[i].top].id,tr[i].id,val);
            for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
                st_update(1,tr[tr[j].top].id,tr[j].id,val);
            if (tr[i].dep>tr[j].dep)
                swap(i,j);
            st_update(1,tr[i].id,tr[j].id,val);
        }
        st_node cty(st_node stn)
        {
            swap(stn.l,stn.r);
            swap(stn.lans,stn.rans);
            return stn;
        }
        int ask(int x,int y)
        {
            int i,j,lcan=lca(x,y);
            st_node ians,jans,ans;
            ians.iflz=jans.iflz=0;
            ians.empt=jans.empt=1;
            for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
                ians=merge(st_ask(1,tr[tr[i].top].id,tr[i].id),ians);
            for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
                jans=merge(st_ask(1,tr[tr[j].top].id,tr[j].id),jans);
            if (tr[i].dep>tr[j].dep)
                swap(i,j),swap(ians,jans);
            jans=merge(st_ask(1,tr[i].id,tr[j].id),jans);
            ans=merge(cty(jans),ians);
            return ans.ans;
        }
        
        int n,m;
        
        void main()
        {
            scanf("%d",&n);
            for (int i=1;i<=n;i++)
                scanf("%d",&data[i]);
            for (int i=1;i<=n;i++)
                tr[i].s.clear();
            for (int i=1;i<n;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                tr[x].s.push_back(y);
                tr[y].s.push_back(x);
            }
            if (n>0)
                tr_build();
            st_build(1,1,cnt);
            scanf("%d",&m);
            for (int i=1;i<=m;i++)
            {
                int K,x,y;
                scanf("%d%d%d",&K,&x,&y);
                if (K==1)
                    printf("%d ",ask(x,y));
                else if (K==2)
                {
                    int val;
                    scanf("%d",&val);
                    update(x,y,val);
                }
            }
            printf("\n");
        }
    }
    
    int main()
    {
        dts::main();
    }
    
  • @ 2020-10-22 22:14:13

    為什麼區間長度不能用深度計算?
    這是錯誤的:

        class st_node
        {
            public:
                int l,r,mid,empt=1;
                int lans=0,rans=0,ans=0,sum=0;
                int iflz=0,numlz;
                int len()
                {
                    return tr[r].dep-tr[l].dep+1;
                }
        };
    

    這是正確的:

        class st_node
        {
            public:
                int l,r,mid,empt=1;
                int lans=0,rans=0,ans=0,sum=0;
                int iflz=0,numlz;
                int len()
                {
                    return r-l+1;
                }
        };
    
    • @ 2020-10-23 09:36:20

      用深度計算(正確方式):

          class st_node
          {
              public:
                  int l,r,mid,empt=1;
                  int lans=0,rans=0,ans=0,sum=0;
                  int iflz=0,numlz;
                  int len()
                  {
                      return tr[rk[r]].dep-tr[rk[l]].dep+1;
                  }
          };
      
      
  • @ 2020-10-22 22:12:24

    剛才AC了
    Accepted
    /in/foo.cc: In function 'void dts::tr_dfs1(int, int, int)':
    /in/foo.cc:28:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i=0;i<tr[now].s.size();i++)
    ~^~~~~~~~~~~~~~~~~
    /in/foo.cc: In function 'void dts::tr_dfs2(int, int)':
    /in/foo.cc:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i=0;i<tr[now].s.size();i++)
    ~^~~~~~~~~~~~~~~~~

    狀態 耗時 記憶體佔用

    #1 Accepted 16ms 26.785 MiB
    #2 Accepted 15ms 26.789 MiB
    #3 Accepted 15ms 26.785 MiB
    #4 Accepted 168ms 30.414 MiB
    #5 Accepted 163ms 30.312 MiB
    #6 Accepted 166ms 30.344 MiB
    #7 Accepted 166ms 30.336 MiB
    #8 Accepted 356ms 34.043 MiB
    #9 Accepted 359ms 33.945 MiB
    #10 Accepted 335ms 33.965 MiB

    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <limits>
    using namespace std;
    
    namespace dts
    {
        int ft=1,cnt;
        class tree_node
        {
            public:
                int fa,dep,size,hs,top,id;
                vector<int> s;
        };
        int rk[(1<<17)+1];
        tree_node tr[(1<<17)+1];
        void tr_dfs1(int now,int fa,int dep)
        {
            tr[now].fa=fa;
            tr[now].dep=dep;
            tr[now].size=1;
            tr[now].hs=-1;
            for (int i=0;i<tr[now].s.size();i++)
                if (tr[now].s[i]!=fa)
                {
                    int next=tr[now].s[i];
                    tr_dfs1(next,now,dep+1);
                    tr[now].size+=tr[next].size;
                    if (tr[now].hs==-1)
                        tr[now].hs=next;
                    else if (tr[tr[now].hs].size<tr[next].size)
                        tr[now].hs=next;
                }
        }
        void tr_dfs2(int now,int top)
        {
            tr[now].top=top;
            tr[now].id=++cnt;
            rk[cnt]=now;
            if (tr[now].hs!=-1)
            {
                tr_dfs2(tr[now].hs,top);
                for (int i=0;i<tr[now].s.size();i++)
                    if (tr[now].s[i]!=tr[now].fa&&tr[now].s[i]!=tr[now].hs)
                        tr_dfs2(tr[now].s[i],tr[now].s[i]);
            }
        }
        void tr_build()
        {
            cnt=0;
            tr_dfs1(ft,ft,1);
            tr_dfs2(ft,ft);
        }
        int lca(int x,int y)
        {
            while (tr[x].top!=tr[y].top)
            {
                if (tr[tr[x].top].dep<tr[tr[y].top].dep)
                    swap(x,y);
                x=tr[tr[x].top].fa;
            }
            if (tr[x].dep<tr[y].dep)
                return x;
            else
                return y;
        }
        
        class st_node
        {
            public:
                int l,r,mid,empt=1;
                int lans=0,rans=0,ans=0,sum=0;
                int iflz=0,numlz;
                int len()
                {
                    return r-l+1;
                }
        };
        int data[(1<<17)+1];
        st_node st[(1<<19)+2];
        #define lc(now) ((now)<<1)
        #define rc(now) ((now)<<1|1)
        st_node merge(st_node li,st_node ri)//li:左子區間,ri:右子區間
        {
            if (li.empt)
                return ri;
            else if (ri.empt)
                return li;
            st_node a;
            a.empt=a.iflz=0;
            a.l=li.l,a.r=ri.r,a.mid=li.r;
            a.lans=max(li.lans,li.sum+ri.lans);
            a.rans=max(ri.rans,ri.sum+li.rans);
            a.ans=max(max(li.ans,ri.ans),li.rans+ri.lans);
            a.sum=li.sum+ri.sum;
            return a;
        }
        void st_pushup(int now)
        {
            st[now]=merge(st[lc(now)],st[rc(now)]);//別在意時間複雜度常數
        }
        void st_update(int now,int l,int r,int val);
        void st_pushdown(int now)
        {
            if (st[now].iflz)
            {
                st_update(lc(now),st[now].l,st[now].mid,st[now].numlz);
                st_update(rc(now),st[now].mid+1,st[now].r,st[now].numlz);
                st[now].iflz=0;
            }
        }
        void st_update(int now,int l,int r,int val)
        {
            if (st[now].l==l&&r==st[now].r)
            {
                st[now].lans=st[now].rans=st[now].ans=max(st[now].len()*val,0);
                st[now].sum=st[now].len()*val;
                st[now].iflz=1,st[now].numlz=val;
            }
            else
            {
                st_pushdown(now);
                if (r<=st[now].mid)
                    st_update(lc(now),l,r,val);
                else if (st[now].mid+1<=l)
                    st_update(rc(now),l,r,val);
                else
                    st_update(lc(now),l,st[now].mid,val),st_update(rc(now),st[now].mid+1,r,val);
                st_pushup(now);
            }
        }
        st_node st_ask(int now,int l,int r)
        {
            if (st[now].l==l&&r==st[now].r)
                return st[now];
            else
            {
                st_pushdown(now);
                if (r<=st[now].mid)
                    return st_ask(lc(now),l,r);
                else if (st[now].mid+1<=l)
                    return st_ask(rc(now),l,r);
                else
                    return merge(st_ask(lc(now),l,st[now].mid),st_ask(rc(now),st[now].mid+1,r));
            }
        }
        void st_build(int now,int l,int r)
        {
            st[now].empt=st[now].iflz=0;
            st[now].l=l,st[now].r=r;
            if (l<r)
            {
                st[now].mid=(l+r)>>1;
                st_build(lc(now),l,st[now].mid);
                st_build(rc(now),st[now].mid+1,r);
                st_pushup(now);
            }
            else
            {
                st[now].sum=data[rk[l]];
                st[now].lans=st[now].rans=st[now].ans=max(data[rk[l]],0);
            }
        }
        
        void update(int x,int y,int val)
        {
            int i,j,lcan=lca(x,y);
            for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
                st_update(1,tr[tr[i].top].id,tr[i].id,val);
            for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
                st_update(1,tr[tr[j].top].id,tr[j].id,val);
            if (tr[i].dep>tr[j].dep)
                swap(i,j);
            st_update(1,tr[i].id,tr[j].id,val);
        }
        st_node cty(st_node stn)
        {
            swap(stn.l,stn.r);
            swap(stn.lans,stn.rans);
            return stn;
        }
        int ask(int x,int y)
        {
            int i,j,lcan=lca(x,y);
            st_node ians,jans,ans;
            ians.iflz=jans.iflz=0;
            ians.empt=jans.empt=1;
            for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
                ians=merge(st_ask(1,tr[tr[i].top].id,tr[i].id),ians);
            for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
                jans=merge(st_ask(1,tr[tr[j].top].id,tr[j].id),jans);
            if (tr[i].dep>tr[j].dep)
                swap(i,j),swap(ians,jans);
            jans=merge(st_ask(1,tr[i].id,tr[j].id),jans);
            ans=merge(cty(jans),ians);
            return ans.ans;
        }
        
        int n,m;
        
        void main()
        {
            scanf("%d",&n);
            for (int i=1;i<=n;i++)
                scanf("%d",&data[i]);
            for (int i=1;i<=n;i++)
                tr[i].s.clear();
            for (int i=1;i<n;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                tr[x].s.push_back(y);
                tr[y].s.push_back(x);
            }
            if (n>0)
                tr_build();
            st_build(1,1,cnt);
            scanf("%d",&m);
            for (int i=1;i<=m;i++)
            {
                int K,x,y;
                scanf("%d%d%d",&K,&x,&y);
                if (K==1)
                    printf("%d ",ask(x,y));
                else if (K==2)
                {
                    int val;
                    scanf("%d",&val);
                    update(x,y,val);
                }
            }
            printf("\n");
        }
    }
    
    int main()
    {
        dts::main();
    }
    
  • 1

信息

ID
1620
难度
8
分类
树结构 | 树链剖分 点击显示
标签
(无)
递交数
807
已通过
111
通过率
14%
上传者