ZJT's Blog

大変に気分がいい~

[自选题 #142] 简单树题

2018-1-7 18:552018-1-7 18:55
集训队作业自选题kd-tree点分治

传送门

一开始直接想歪了,想到点分那边去了。。。接着就发现这tm要维护二维平面啊,这不是得写kd树吗。然后就很脑抽的写了一个点分树套kd树。。。估计这题用了kd树的就我这个zz。。。

考虑动态点分治,每次改边权,对于点分树到根路径上的每个点,都会影响一整棵子树。子树的话肯定用dfs序处理,但是这题的询问区间是跟原编号相关的。所以我们就对点分树上的每个节点维护一棵kd树,维护对应的所有点组成的关于原编号和dfs序的二维平面。这样一次操作的复杂度就是$O(\sqrt n)+O(\sqrt{n/2})+O(\sqrt{n/4})+\cdots=O(\sqrt{n})$,所以总复杂度就是$O(m\sqrt n)$啦。

然而这题正解好像是$O(m\sqrt n\log n)$的。。。然后我的根号做法竟然还被碾了(大概是因为kd树常数过于玄学),一直TLE卡不过去。最后把同一份代码反复交了22次之后竟然过了,刚好用完所有提交机会,分数在80~100之间随机。。。tuoj怕是真实土豆评测机。。。

#include <bits/stdc++.h>
#define MAXN 70010
#define LL long long
using namespace std;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res;
}

struct edge{
    int to,next,w;
    edge(int _to=0,int _next=0,int _w=0):to(_to),next(_next),w(_w){}
}e[MAXN<<1];

int n,m,type;
int g[MAXN],nume;
int size[MAXN],maxs[MAXN],pre[MAXN];
int e2[MAXN][3];
int w[MAXN][20][3],w2[MAXN][20][2],ls[MAXN];
bool visit[MAXN];
int root,sums;
int debug=0;

struct KDTree{
    int n,root;
    int *xmin,*xmax,*ymin,*ymax,*px,*py,*lc,*rc,*size,*pre;
    LL *tag,*s,*v;
    int sz;
    static int p[MAXN],nump;
    static int w[MAXN][2],numw;
    static LL v0[MAXN];

    static bool cmpx(int x,int y){ return x<y; }
    static bool cmpy(int x,int y){ return w[x][0]<w[y][0]; }

    void dfs(int x,int pre){
        ::w[x][++ls[x]][0]=w[x][0]=++numw;
        p[++nump]=x;
        for(int i=g[x];~i;i=e[i].next)
            if(!visit[e[i].to] && e[i].to!=pre){
                v0[e[i].to]=v0[x]+e[i].w;
                dfs(e[i].to,x);
            }
        ::w[x][ls[x]][1]=w[x][1]=numw;
    }

    void dfs2(int x,int p,int t1,int t2){
        ::w2[x][ls[x]][0]=t1;
        ::w2[x][ls[x]][1]=t2;
        for(int i=g[x];~i;i=e[i].next)
            if(!visit[e[i].to] && e[i].to!=p)
                dfs2(e[i].to,x,t1,t2);
    }

    int build(int l,int r,int d){
        if(l>r) return 0;
        int mid=(l+r)>>1;
        if(d==0) nth_element(p+l,p+mid,p+r+1,cmpx);
        else nth_element(p+l,p+mid,p+r+1,cmpy);
        int x=++sz;
        ::w[p[mid]][ls[p[mid]]][2]=x;
        xmin[x]=xmax[x]=px[x]=p[mid]; ymin[x]=ymax[x]=py[x]=w[p[mid]][0];
        lc[x]=build(l,mid-1,d^1);
        rc[x]=build(mid+1,r,d^1);
        if(lc[x]){
            xmin[x]=min(xmin[x],xmin[lc[x]]);
            ymin[x]=min(ymin[x],ymin[lc[x]]);
            xmax[x]=max(xmax[x],xmax[lc[x]]);
            ymax[x]=max(ymax[x],ymax[lc[x]]);
        }
        if(rc[x]){
            xmin[x]=min(xmin[x],xmin[rc[x]]);
            ymin[x]=min(ymin[x],ymin[rc[x]]);
            xmax[x]=max(xmax[x],xmax[rc[x]]);
            ymax[x]=max(ymax[x],ymax[rc[x]]);
        }
        v[x]=v0[p[mid]];
        size[x]=1+size[lc[x]]+size[rc[x]];
        s[x]=v[x]+s[lc[x]]+s[rc[x]];
        if(lc[x]) pre[lc[x]]=x;
        if(rc[x]) pre[rc[x]]=x;
        return x;
    }

    void pushdown(int x){
        if(!tag[x]) return;
        if(lc[x]){
            tag[lc[x]]+=tag[x];
            v[lc[x]]+=tag[x];
            s[lc[x]]+=tag[x]*size[lc[x]];
        }
        if(rc[x]){
            tag[rc[x]]+=tag[x];
            v[rc[x]]+=tag[x];
            s[rc[x]]+=tag[x]*size[rc[x]];
        }
        tag[x]=0;
    }

    void modify(int x,int y1,int y2,LL dv){
        if(y1<=ymin[x] && y2>=ymax[x]){
            tag[x]+=dv;
            s[x]+=dv*size[x];
            v[x]+=dv;
            return;
        }
        pushdown(x);
        if(y1<=py[x] && y2>=py[x]) v[x]+=dv;
        if(lc[x] && y1<=ymax[lc[x]] && y2>=ymin[lc[x]])
            modify(lc[x],y1,y2,dv);
        if(rc[x] && y1<=ymax[rc[x]] && y2>=ymin[rc[x]])
            modify(rc[x],y1,y2,dv);
        s[x]=v[x]+s[lc[x]]+s[rc[x]];
    }

    void query(int x,int x1,int x2,int y1,int y2,LL &res1,int &res2){
        if(!x || x1>xmax[x] || x2<xmin[x] || y1>ymax[x] || y2<ymin[x]) return;
        if(x1<=xmin[x] && x2>=xmax[x] && y1<=ymin[x] && y2>=ymax[x]){
            res1+=s[x],res2+=size[x];
            return;
        }
        pushdown(x);
        if(x1<=px[x] && x2>=px[x] && y1<=py[x] && y2>=py[x]) res1+=v[x],res2++;
        query(lc[x],x1,x2,y1,y2,res1,res2);
        query(rc[x],x1,x2,y1,y2,res1,res2);
    }

    LL getV(int x){
        LL res=v[x];
        for(x=pre[x];x;x=pre[x]) res+=tag[x];
        return res;
    }

    void init(int _n,int _root){
        n=_n;
        xmin=new int[n+1];
        xmax=new int[n+1];
        ymin=new int[n+1];
        ymax=new int[n+1];
        px=new int[n+1];
        py=new int[n+1];
        lc=new int[n+1];
        rc=new int[n+1];
        size=new int[n+1];
        pre=new int[n+1];
        tag=new LL[n+1];
        s=new LL[n+1];
        v=new LL[n+1];
        for(int i=0;i<=n;i++) s[i]=v[i]=tag[i]=0;
        size[0]=0;
        nump=numw=0;
        v0[_root]=0;
        dfs(_root,0);
        for(int i=g[_root];~i;i=e[i].next)
            if(!visit[e[i].to])
                dfs2(e[i].to,_root,w[e[i].to][0],w[e[i].to][1]);
        root=build(1,n,1);
    }
}a[MAXN];

int KDTree::p[MAXN],KDTree::nump;
int KDTree::w[MAXN][2],KDTree::numw;
LL KDTree::v0[MAXN];

void addEdge(int u,int v,int w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
}

void findRoot(int x,int p){
    size[x]=1; maxs[x]=0;
    for(int i=g[x];~i;i=e[i].next)
        if(!visit[e[i].to] && e[i].to!=p){
            findRoot(e[i].to,x);
            size[x]+=size[e[i].to];
            if(size[e[i].to]>maxs[x]) maxs[x]=size[e[i].to];
        }
    if(sums-size[x]>maxs[x]) maxs[x]=sums-size[x];
    if(maxs[x]<maxs[root]) root=x;
}

void build(int x){
    visit[x]=1;
    findRoot(x,0);
    a[x].init(sums,x);
    for(int i=g[x];~i;i=e[i].next)
        if(!visit[e[i].to]){
            root=0; sums=size[e[i].to];
            findRoot(e[i].to,0);
            pre[root]=x;
            build(root);
        }
}

void modify(int eid,int v){
    int y=e2[eid][1],x=e2[eid][0];
    int lx=ls[x],ly=ls[y];
    int tx=x,ty=y;
    while(ls[ty]>ls[tx]) ty=pre[ty],ly--;
    while(ls[ty]<ls[tx]) tx=pre[tx],lx--;
    while(tx!=ty) tx=pre[tx],ty=pre[ty],lx--,ly--;
    for(;tx;tx=pre[tx],lx--,ly--){
        if(w[x][lx][0]<w[y][ly][0]) swap(x,y);
        a[tx].modify(1,w[x][lx][0],w[x][lx][1],v-e2[eid][2]);
    }
    e2[eid][2]=v;
}

LL query(int x,int l,int r){
    LL res=0;
    int zjtsb;
    a[x].query(1,l,r,1,a[x].n,res,zjtsb);
    int cl=ls[x]-1;
    for(int y=pre[x];y;y=pre[y],cl--){
        int p1=w2[x][cl][0],p2=w2[x][cl][1],res2=0;
        LL res1=0,temp=0;
        a[y].query(1,l,r,1,p1-1,res1,res2);
        if(p2<a[y].n) a[y].query(1,l,r,p2+1,a[y].n,res1,res2);
        temp=a[y].getV(w[x][cl][2]);
        res+=res1+res2*temp;
    }
    return res;
}

int main(){
#ifdef DEBUG
    freopen("142.in","r",stdin);
    freopen("142.out","w",stdout);
#endif
    memset(g,-1,sizeof g);
    maxs[0]=0x7FFFFFFF;
    scanf("%d%d%d",&n,&m,&type);
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        e2[i][0]=u; e2[i][1]=v; e2[i][2]=w;
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    root=0; sums=n;
    findRoot(1,0);
    build(root);
    LL lastans=0;
    while(m--){
        char c;
        while((c=getchar())!='q' && c!='m');
        if(c=='q'){
            int l=read(),r=read(),x=read();
            if(type) l^=lastans,r^=lastans,x^=lastans;
            printf("%lld\n",lastans=query(x,l,r));
            lastans%=n;
        }else{
            int x=read(),y=read();
            if(type) x^=lastans,y^=lastans;
            modify(x,y);
        }
    }
    return 0;
}

查看详细内容

[自选题 #140] Swap

2018-1-5 15:272018-1-5 15:28
集训队作业自选题贪心

传送门

他既然要求字典序最小,那我们就一个个大力贪心模拟选哪个就好了。对于每个点,它跟儿子的交换可能是确定的,可能是不确定的(当右儿子小于左儿子的时候就不确定,因为不知道交换完之后左右儿子分别对应哪个值会比较优,需要留到后面处理)。从小到大考虑每个点,我们沿着不确定的点一直向上走,就能得到这个点可能取到的值。因为字典序要最小,所以我们选其中最小的一个值。这时候有三种情况,一个是这个最小值比左儿子大,且左儿子小于右儿子,这时最优的方案显然是把这个点跟左儿子交换;第二种情况是最小值大于右儿子,且右儿子小于左儿子,这时的情况就不确定了,但这个点取到的值一定就是右儿子的值,剩下两个值怎么分配留到后面去处理;最后一种情况就是不跟儿子交换,直接取上面换下来的值,这样我们就可以一路往上,把所有不确定方向的点都改为确定方向,直到碰到那个最小值的点为止。这样就在$O(n\log n)$的时间内做完了。

感觉这题可以出到一般的二叉树上?把暴力跳换成数据结构是不是就行了呢?

#include <cstdio>
#include <cstring>
#define MAXN 200010

int n;
int v[MAXN],v2[MAXN],d[MAXN];

int gao(int x){
    int minv=n+1;
    for(int i=x>>1,j=x;;i>>=1,j>>=1){
        if(d[i]==-1){
            if(v2[i]<minv) minv=v2[i];
        }else if(i*2+d[i]!=j){
            if(v[j]<minv) minv=v[j];
            break;
        }
    }
    int c1=x<<1,c2=x<<1|1;
    if(c1>n) c1=0;
    if(c2>n) c2=0;
    if(minv<v[c1] && minv<v[c2]){
        d[x]=2;
        v2[x]=n+1;
        for(int i=x>>1,j=x;;i>>=1,j>>=1){
            if(d[i]==-1){
                if(v2[i]!=minv){
                    d[i]=j-i*2;
                    v[j^1]=v2[i];
                }else{
                    d[i]=(j-i*2)^1;
                    v[j]=v2[i];
                    break;
                }
            }else if(i*2+d[i]!=j){
                d[j]=2;
                break;
            }
        }
        return minv;
    }else if(v[c1]<v[c2]){
        d[x]=0;
        v2[x]=v[c2];
        return v[c1];
    }else{
        v2[x]=v[c1];
        return v[c2];
    }
}

int main(){
#ifdef DEBUG
    freopen("140.in","r",stdin);
#endif
    scanf("%d",&n);
    v[0]=n+1;
    memset(d,-1,sizeof d);
    d[0]=2;
    for(int i=1;i<=n;i++) scanf("%d",v+i);
    for(int i=1;i<=n;i++) printf("%d ",gao(i));
    return 0;
}

查看详细内容

[自选题 #111] 资源采集

2018-1-5 15:182018-1-5 15:18
集训队作业自选题kd-tree

传送门

这题北京集训的时候做过。。。

大概就是先按dfs序和深度把每个点表示在一个二维平面上,然后一个询问覆盖到的点就是一个矩形内的点。我们把这些点的KD树建出来,这样每次询问覆盖到的节点数量就是$O(\sqrt n)$级别的。操作之后的节点我们可以打上标记,然后如果一次询问中发现子树里面存在之前的标记,就暴力搜索下去,把标记都清除,并更新答案。这样每添加一个标记,最多会花费$O(\log n)$的时间去清除它(这个log是KD树的树高)。所以总复杂度就是$O(n\sqrt n\log n)$的。相信KD树常数很小的话就能过啦!

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
#define LL long long
#define MAXN 100010
using namespace std;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9')
        res=res*10+c-'0';
    return res;
}

struct edge{
    int to,next;
    LL w;
    edge(int _to=0,int _next=0,LL _w=0):to(_to),next(_next),w(_w){}
}e[MAXN<<1];

int n,m;
int w[MAXN][2],numw=0;
int g[MAXN],nume=0;
LL v[MAXN],lim[MAXN],d[MAXN];
LL q[MAXN][3];
int p[MAXN];

int debug=0;

namespace SegTree{
    struct node{
        LL s1,s2;
        int lc,rc;
    }a[7000000];

    int size;
    LL sizew;

    void init(){
        size=0;
        memset(a,0,sizeof a);
        for(int i=1;i<=n;i++)
            sizew=max(sizew,(lim[i]-1)/v[i]+1);
    }

    int create(int l,int r,int p,LL v1,LL v2){
        int x=++size;
        a[x].s1=v1;
        a[x].s2=v2;
        if(l==r) return x;
        int mid=(l+r)>>1;
        if(p<=mid) a[x].lc=create(l,mid,p,v1,v2);
        else a[x].rc=create(mid+1,r,p,v1,v2);
        return x;
    }

    int join(int x,int y){
        if(!x) return y;
        if(!y) return x;
        int z=++size;
        a[z].s1=a[x].s1+a[y].s1;
        a[z].s2=a[x].s2+a[y].s2;
        a[z].lc=join(a[x].lc,a[y].lc);
        a[z].rc=join(a[x].rc,a[y].rc);
        return z;
    }

    LL getS1(int x,int l,int r,int cl,int cr){
        if(l<=cl && cr<=r) return a[x].s1;
        int mid=(cl+cr)>>1;
        LL res=0;
        if(l<=mid)
            res+=getS1(a[x].lc,l,r,cl,mid);
        if(r>mid)
            res+=getS1(a[x].rc,l,r,mid+1,cr);
        return res;
    }

    LL getS2(int x,int l,int r,int cl,int cr){
        if(l<=cl && cr<=r) return a[x].s2;
        int mid=(cl+cr)>>1;
        LL res=0;
        if(l<=mid)
            res+=getS2(a[x].lc,l,r,cl,mid);
        if(r>mid)
            res+=getS2(a[x].rc,l,r,mid+1,cr);
        return res;
    }
}

namespace KD_Tree{
    struct point{
        int id;
        LL x,y;
        LL t1,t2,t3;
    }p[MAXN];

    bool cmpx(point x,point y){ return x.x<y.x; }
    bool cmpy(point x,point y){ return x.y<y.y; }

    struct node{
        int lc,rc,p,l,r;
        int seg_root;
        bool tag;
        LL delta_t;
        LL minx,maxx,miny,maxy;
    }a[MAXN<<1];

    int size;
    LL total_delta_t;

    int build(int l,int r,int d){
        if(!d)
            sort(p+l,p+r+1,cmpx);
        else
            sort(p+l,p+r+1,cmpy);
        int x=++size;
        a[x].l=l;
        a[x].r=r;
        a[x].minx=a[x].maxx=p[l].x;
        a[x].miny=a[x].maxy=p[l].y;
        for(int i=l+1;i<=r;i++){
            if(p[i].x<a[x].minx) a[x].minx=p[i].x;
            if(p[i].x>a[x].maxx) a[x].maxx=p[i].x;
            if(p[i].y<a[x].miny) a[x].miny=p[i].y;
            if(p[i].y>a[x].maxy) a[x].maxy=p[i].y;
        }
        if(l==r){
            p[l].t1=(lim[p[l].id]-1)/v[p[l].id]+1;
            p[l].t2=lim[p[l].id];
            p[l].t3=v[p[l].id];
            a[x].seg_root=SegTree::create(1,SegTree::sizew,p[l].t1,p[l].t2,p[l].t3);
            return x;
        }
        int mid=(l+r)>>1;
        a[x].lc=build(l,mid,d^1);
        a[a[x].lc].p=x;
        a[x].rc=build(mid+1,r,d^1);
        a[a[x].rc].p=x;
        a[x].seg_root=SegTree::join(a[a[x].lc].seg_root,a[a[x].rc].seg_root);
        return x;
    }

    void init(){
        SegTree::init();
        memset(a,0,sizeof a);
        for(int i=1;i<=n;i++)
            p[i].x=w[i][0],p[i].y=d[i],p[i].id=i;
        size=0;
        build(1,n,0);
        a[1].p=0;
        total_delta_t=0;
    }

    bool collide(int x,LL minx,LL miny,LL maxx,LL maxy){
        if(minx>a[x].maxx) return 0;
        if(miny>a[x].maxy) return 0;
        if(maxx<a[x].minx) return 0;
        if(maxy<a[x].miny) return 0;
        return 1;
    }

    bool contain(int x,LL minx,LL miny,LL maxx,LL maxy){
        if(minx>a[x].minx) return 0;
        if(miny>a[x].miny) return 0;
        if(maxx<a[x].maxx) return 0;
        if(maxy<a[x].maxy) return 0;
        return 1;
    }

    LL query(int x,LL t){
        if(a[x].r-a[x].l+1<=70){
            LL res=0;
            for(int i=a[x].l;i<=a[x].r;i++)
                res+=(p[i].t1<=t)?(p[i].t2):(p[i].t3*t);
            return res;
        }
        LL res=0;
        if(t)
            res+=SegTree::getS1(a[x].seg_root,1,t,1,SegTree::sizew);
        if(t<SegTree::sizew)
            res+=SegTree::getS2(a[x].seg_root,t+1,SegTree::sizew,1,SegTree::sizew)*t;
        return res;
    }

    LL res_gao;

    void dfs(int x){
        a[x].tag=0;
        if(a[x].delta_t){
            res_gao-=query(x,total_delta_t);
            res_gao+=query(x,total_delta_t+a[x].delta_t);
            a[x].delta_t=0;
        }else{
            if(a[a[x].lc].tag) dfs(a[x].lc);
            if(a[a[x].rc].tag) dfs(a[x].rc);
        }
    }

    LL gao(int x){
        res_gao=query(x,total_delta_t);
        if(a[x].tag)
            dfs(x);
        a[x].delta_t=-total_delta_t;
        a[x].tag=1;
        if(a[x].p && !a[a[x].p].tag){
            for(int i=a[x].p;i;i=a[i].p)
                a[i].tag=1;
        }
        return res_gao;
    }

    void pushdown(int x){
        if(!a[x].delta_t) return;
        a[a[x].lc].tag=1;
        a[a[x].rc].tag=1;
        a[a[x].lc].delta_t=a[x].delta_t;
        a[a[x].rc].delta_t=a[x].delta_t;
        a[x].delta_t=0;
    }

    LL gao(int x,LL minx,LL miny,LL maxx,LL maxy){
        if(!collide(x,minx,miny,maxx,maxy)) return 0;
        if(contain(x,minx,miny,maxx,maxy)) return gao(x);
        pushdown(x);
        LL res=0;
        if(a[x].lc) res+=gao(a[x].lc,minx,miny,maxx,maxy);
        if(a[x].rc) res+=gao(a[x].rc,minx,miny,maxx,maxy);
        return res;
    }
}

void addEdge(int u,int v,LL w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
}

void dfs(int x,int p){
    w[x][0]=++numw;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            d[e[i].to]=d[x]+e[i].w;
            dfs(e[i].to,x);
        }
    w[x][1]=numw;
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("C.in","r",stdin);
    #endif
    memset(g,-1,sizeof g);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        v[i]=read();
    for(int i=1;i<=n;i++)
        lim[i]=read();
    d[1]=d[0]=0;
    for(int i=2;i<=n;i++){
        p[i]=read();
        d[i]=read();
        addEdge(p[i],i,d[i]);
    }
    dfs(1,0);
    KD_Tree::init();
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        q[i][0]=read();
        q[i][1]=read();
        q[i][2]=read();
    }
    for(int i=1;i<=m;i++){
        KD_Tree::total_delta_t=q[i][0];
        printf("%lld\n", KD_Tree::gao(1,w[q[i][1]][0],d[q[i][1]],w[q[i][1]][1],d[q[i][1]]+q[i][2]));
    }
    return 0;
}

查看详细内容

[自选题 #132] Heavy-Light Decomposition

2018-1-5 2:62018-1-5 2:6
集训队作业自选题link-cut tree

传送门

直接暴力用splay维护轻重链就行了,显然改变次数是均摊log的。对LCT的那套势能分析应该也一样适用(不过没仔细研究),所以应该是一个log的(就算不适用也是两个log)。

#include <bits/stdc++.h>
#define MAXN 200010
#define LL long long

struct node{
    int ch[2],p,lp;
    int tag,v,minv;
}a[MAXN];

int n,m;
int ch[MAXN][2],sc[MAXN],cc[MAXN],pre[MAXN],d[MAXN];
int size[MAXN];
LL ans;

void pushdown(int x){
    if(a[x].ch[0]) a[a[x].ch[0]].tag+=a[x].tag,a[a[x].ch[0]].v+=a[x].tag,a[a[x].ch[0]].minv+=a[x].tag;
    if(a[x].ch[1]) a[a[x].ch[1]].tag+=a[x].tag,a[a[x].ch[1]].v+=a[x].tag,a[a[x].ch[1]].minv+=a[x].tag;
    a[x].tag=0;
}

void pushup(int x){
    a[x].minv=a[x].v;
    if(a[x].ch[0] && a[a[x].ch[0]].minv<a[x].minv) a[x].minv=a[a[x].ch[0]].minv;
    if(a[x].ch[1] && a[a[x].ch[1]].minv<a[x].minv) a[x].minv=a[a[x].ch[1]].minv;
}

void rotate(int x){
    int p=a[x].p;
    int d=a[p].ch[0]==x;
    if(a[p].p) a[a[p].p].ch[a[a[p].p].ch[1]==p]=x;
    else{
        a[x].lp=a[p].lp;
        a[p].lp=0;
    }
    a[x].p=a[p].p;
    a[p].ch[d^1]=a[x].ch[d];
    if(a[x].ch[d]) a[a[x].ch[d]].p=p;
    a[x].ch[d]=p;
    a[p].p=x;
    pushup(p);
}

void clearTag(int x){
    static int ls[MAXN];
    int len=0;
    while(x) ls[++len]=x,x=a[x].p;
    while(len) pushdown(ls[len--]);
}

void splay(int x){
    clearTag(x);
    while(a[x].p){
        int p=a[x].p;
        if(!a[p].p) rotate(x);
        else{
            int q=a[p].p;
            if((a[q].ch[1]==p)==(a[p].ch[1]==x)) rotate(p),rotate(x);
            else rotate(x),rotate(x);
        }
    }
    pushup(x);
}

int find(int x){
    pushdown(x);
    if(a[x].ch[1] && a[a[x].ch[1]].minv<0) return find(a[x].ch[1]);
    if(a[x].v<0) return x;
    return find(a[x].ch[0]);
}

void access(int x){
    if(x==1) return;
    if(!(--d[pre[x]])) ans-=cc[pre[x]];
    splay(x);
    if(a[x].ch[0]){
        a[a[x].ch[0]].p=0;
        a[a[x].ch[0]].lp=a[x].lp;
        x=a[x].ch[0];
        a[x].tag--; a[x].v--; a[x].minv--;
        pushdown(x);
        pushup(x);
    }else{
        int t=a[x].lp;
        a[x].lp=0;
        x=t;
        splay(x);
        if(a[x].ch[0]) a[a[x].ch[0]].tag--,a[a[x].ch[0]].v--,a[a[x].ch[0]].minv--;
        a[x].v++;
        pushup(x);
    }
    while(1){
        if(a[x].minv>=0){
            x=a[x].lp;
            if(!x) break;
            splay(x);
            if(a[x].ch[0]) a[a[x].ch[0]].tag--,a[a[x].ch[0]].v--,a[a[x].ch[0]].minv--;
            a[x].v++;
            pushup(x);
            continue;
        }
        x=find(x);
        splay(x);
        ans-=cc[x];
        cc[x]^=sc[x];
        if(d[x]==0) cc[x]=0;
        ans+=cc[x];
        if(a[x].ch[1]){
            a[a[x].ch[1]].lp=x;
            a[a[x].ch[1]].p=0;
        }
        splay(cc[x]);
        a[x].ch[1]=cc[x];
        if(a[x].ch[1]){
            a[a[x].ch[1]].lp=0;
            a[a[x].ch[1]].p=x;
        }
        a[x].v=-a[x].v;
        pushup(x);
    }
}

void dfs(int x){
    size[x]=1;
    if(ch[x][0]) dfs(ch[x][0]),size[x]+=size[ch[x][0]];
    if(ch[x][1]) dfs(ch[x][1]),size[x]+=size[ch[x][1]];
    if(size[x]>1){
        if(size[ch[x][0]]>=size[ch[x][1]]) cc[x]=ch[x][0];
        else cc[x]=ch[x][1];
        ans+=cc[x];
        a[x].v=size[cc[x]]-size[sc[x]^cc[x]];
        a[x].ch[1]=cc[x];
        a[cc[x]].p=x;
        pre[cc[x]]=x;
        d[x]++;
        if(sc[x]^cc[x]) a[sc[x]^cc[x]].lp=x,pre[sc[x]^cc[x]]=x,d[x]++;
        pushup(x);
    }
}

int main(){
#ifdef DEBUG
    freopen("132.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&ch[i][0],&ch[i][1]);
        sc[i]=ch[i][0]^ch[i][1];
    }
    dfs(1);
    printf("%lld\n",ans);
    scanf("%d",&m);
    while(m--){
        int x;
        scanf("%d",&x);
        access(x);
        printf("%lld\n",ans);
    }
}

查看详细内容

[自选题 #136] trip

2018-1-5 1:592018-1-5 2:0
集训队作业自选题树形DP概率与期望

传送门

比较水的树形DP,可以直接统计出一条边走过去之后还能走回来的概率。然后把问题转化成求每个点被经过的概率,以及期望的经过次数就行了。这两个都很好DP。

#include <bits/stdc++.h>
#define MAXN 1000010
#define LL long long

const LL P=998244353;

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n;
int c[MAXN],d[MAXN];
int g[MAXN],nume;
LL w1[MAXN],w2[MAXN],w3[MAXN];
LL sw2[MAXN];
LL inv_v[MAXN];

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void dfs(int x,int p){
    LL temp=0;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            dfs(e[i].to,x);
            temp=(temp+w1[e[i].to]);
        }
    w3[x]=temp;
    if(p){
        if(d[x]==1) return;
        temp=temp*inv_v[d[x]]%P;
        w1[x]=getPow(1-temp,P-2)*inv_v[d[x]]%P;
    }
}

void dfs2(int x,int p){
    LL temp=p?w2[x]:0;
    w3[x]=(w3[x]+w2[x])*inv_v[d[x]]%P;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p)
            temp=(temp+w1[e[i].to])%P;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            LL temp2=(temp-w1[e[i].to])*inv_v[d[x]]%P;
            w2[e[i].to]=getPow(1-temp2,P-2)*inv_v[d[x]]%P;
            sw2[e[i].to]=sw2[x]*w2[e[i].to]%P;
            dfs2(e[i].to,x);
        }
}

int main(){
#ifdef DEBUG
    freopen("136.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    inv_v[1]=1;
    for(int i=2;i<MAXN;i++) inv_v[i]=inv_v[P%i]*(P-P/i)%P;
    scanf("%d",&n);
    static char str[MAXN];
    scanf("%s",str+1);
    for(int i=1;i<=n;i++) c[i]=str[i]=='1';
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
        d[u]++; d[v]++;
    }
    dfs(1,0);
    sw2[1]=1;
    dfs2(1,0);
    LL ans=0;
    for(int i=1;i<=n;i++)
        if(c[i]==0 || d[i]==1){
            ans=(ans+sw2[i])%P;
        }else{
            LL temp=getPow(1-w3[i],P-2);
            temp=temp%P*sw2[i]%P;
            ans=(ans+temp)%P;
        }
    ans=(ans%P+P)%P;
    printf("%lld\n",ans);
}

查看详细内容