UOJ Logo RAcceleratorPlus的博客

博客

tg D2T3 线性做法

2015-11-10 16:49:09 By RAcceleratorPlus

我知道这是一道傻逼题...但是考场上并没有调出来...我还没有打暴力...恩..考挂自己弱...

先考虑一条链的情况...我们发现,最优解肯定要考虑减小最长链,其次考虑次长的,...那么我们设$L_i$为第i长的链,我们需要删去的一条边一定是对于某个正整数k,$\bigcup_{i=1}^kL_i$上的最长边,那么我们把这些区间处理出来每次更新,就有了一个复杂度为$O(n)$的优秀算法.

对于一棵树的情况,考虑处理出它的最长链,在这条链上做就可以了.

yyhs数据有一个点我比他优? 感觉是我写炸了...窝要去调调...

考场代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
///ri gou qu ba CCF
inline int max(int a,int b){
    if(a<b) return b; else return a;
}
#define maxn 300010
struct sw{
    int nx[maxn];
    int si;
    inline int qmaxe(int n,int e){
        if(n==si) return nx[1]-e; else return max(nx[1]-e,nx[n+1]);
    }
    inline int push(int n){
        ++si;
        nx[si]=n;
    }
} sww;
struct ed{
    int t,n,v;
} fy[maxn*2];
int h[maxn],sie;
inline void ae(int f,int t,int v){
    ++sie;
    fy[sie]=(ed){t,h[f],v};
    h[f]=sie;
}
inline int l2e(int a){
    float p=(float)a;
    return (((*(int*)&p)>>23)+1)&31;
}
struct tree{
    int fa[maxn],de[maxn],deu[maxn],si;
    int seq[maxn*4],seqL,reseq[maxn];
    int st[maxn*4][21];
    inline void logSeq(int n){ seq[seqL++]=n; }
    inline void dfsBuild(int nw,int fax,int fad,int dex){
        de[nw]=fad,deu[nw]=dex,fa[nw]=fax;
        reseq[nw]=seqL;
        logSeq(nw);
        for(int i=h[nw],_;i;i=fy[i].n){
            _=fy[i].t;
            if(_==fa[nw]) continue;
            dfsBuild(_,nw,fad+1,dex+fy[i].v);
            logSeq(nw);
        }
    }
    inline int mindep(int a,int b){
        if(de[a]<de[b]) return a; else return b;
    }
    inline void genSt(){
        int t=l2e(seqL);
        for(int i=0;i<seqL;++i) st[i][0]=seq[i];
        for(int i=2,j=1;i<=seqL;i<<=1,++j){
            register int q=i>>1;
            for(int k=0,_=seqL-i;k<=_;++k){
                st[k][j]=mindep(st[k][j-1],st[k+q][j-1]);
            }
        }
    }
    inline int getmin(int a,int b){
        if(b<a) std::swap(a,b);
        int l=b-a+1;
        int le=l2e(l);
        int lk=1<<le;
        return mindep(st[a][le],st[b-le+1][le]);
    }
    inline int LCA(int a,int b){
        return getmin(reseq[a],reseq[b]);
    }
    inline void build(int n){
        si=n;
        dfsBuild(1,0,0,0);genSt();
    }
    int impPoints[maxn],impL,blt[maxn];//important points, (length), belongs to
    int impDs[maxn],mxl,mxr,mxn;
    bool ft;
    inline int getMax(int l,int r){
        if(!ft){
            mxl=l,mxr=l-1;
            ft=1;
        } 
        while(mxl>l){
            --mxl;
            mxn=max(impDs[mxl],mxn);
        }
        while(mxr<r){
            ++mxr;
            mxn=max(impDs[mxr],mxn);
        }
    }
    int resSes;
    inline void dfsResec(int nq,int fa){
        blt[nq]=resSes;
        for(int t=h[nq],_;t;t=fy[t].n){
            if(_==fa) continue;
            dfsResec(_,nq);
        }
    }
    inline void resec(int n){
        resSes=n;
        blt[impPoints[n]]=n;
        for(int t=h[impPoints[n]],_;t;t=fy[t].n){
            _=fy[t].t;
            if(_==impPoints[n-1]) continue;
            if(_==impPoints[n+1]) continue;
            dfsResec(_,impPoints[n]);
        }
    }
} tr;
struct path{
    int f,t,p,len;
    path(int f=0,int t=0):f(f),t(t){}
    inline int lengthTot(){
        p=tr.LCA(f,t);
        return tr.deu[f]+tr.deu[t]-(tr.deu[p]<<1);
    }
    inline void rd(){
        scanf("%d%d",&f,&t);
        len=lengthTot();
    }
} paa[maxn];
inline bool cmp(const path& a,const path& b){
    return a.len<b.len;
}
int n,m,imps[maxn],sl;
inline void ps1(int n){
    ++tr.impL;
    tr.impPoints[tr.impL]=n;
}
inline void psl(int n){
    static int s=1;
    tr.impDs[s]=n;
    ++s;
}
inline void ps2(int n){
    ++sl;
    imps[sl]=n;
}
inline void getImpPo(){//get important points
    int tx=paa[1].f;
    while(tx!=paa[1].p){
        ps1(tx);
        psl(tr.deu[tx]-tr.deu[tr.fa[tx]]);
        tx=tr.fa[tx];
    }
    ps1(paa[1].p);
    tx=paa[1].t;
    while(tx!=paa[1].p){
        ps2(tx);
    }
    while(sl){
        tx=imps[sl];
        ps1(tx);
        psl(tr.deu[tx]-tr.deu[tr.fa[tx]]);
        --sl;
    }
}
struct range{
    int l,r;
    bool valid;
    inline range(int l=0,int r=0,bool testValid=1):l(l),r(r){
        if(testValid) if(l>r) std::swap(l,r);
    }
    inline range operator*(range b){ // intersect
        range p(l,r,0);
        if(b.l>l) p.l=b.l;
        if(b.r<r) p.r=b.r;
        return p;
    }
    inline bool hasRg(){
        return r>=l;
    }
} rgs[maxn];
int rgl;
inline void pushRange(range f){
    rgs[++rgl]=f;
}
inline range top(){
    return rgs[rgl];
}
inline bool same(range a,range b){
    return a.l==b.l && a.r==b.r;
}
inline void rt(){
    scanf("%d%d",&n,&m);
    for(int i=1,a,b,v;i<n;++i){
        scanf("%d%d%d",&a,&b,&v);
        ae(a,b,v); ae(b,a,v);
    }
    tr.build(n);
    for(int i=1;i<=m;++i) paa[i].rd();
    std::sort(paa+1,paa+m+1,cmp);
    getImpPo();
    for(int i=1;i<=m;++i) sww.push(paa[i].len);
    for(int i=1;i<=m;++i){
        pushRange(top()*range(tr.blt[paa[i].f],tr.blt[paa[i].t]));
    }
}
inline void tensen(int &a,int b){
    if(a>b) a=b;
}
int main(){
    freopen("transport.in","r",stdin);
    freopen("transport.out","w",stdout);
    rt();
    int i=m;
    int maxp=0x7fffffff;
    while(!rgs[i].hasRg()){ --i; }
    while(i){
        tensen(maxp,sww.qmaxe(i,tr.getMax(rgs[i].l,rgs[i].r)));
        --i;
    }
    printf("%d\n",maxp);
    return 0;
}

调出来的代码

#include <cstdio>
#include <algorithm>
#include <cstring>
///ri gou qu ba CCF
inline int max(int a,int b){
    if(a<b) return b; else return a;
}
#define maxn 300010
struct sw{
    int nx[maxn];
    int si;
    inline int qmaxe(int n,int e){
        if(n==si) return nx[1]-e; else return max(nx[1]-e,nx[n+1]);
    }
    inline int push(int n){
        ++si;
        nx[si]=n;
    }
} sww;
struct ed{
    int t,n,v;
} fy[maxn*2];
int h[maxn],sie;
inline void ae(int f,int t,int v){
    ++sie;
    fy[sie]=(ed){t,h[f],v};
    h[f]=sie;
}
inline int l2e(int a){
    float p=(float)a;
    return (((*(int*)&p)>>23)+1)&31;
}
struct tree{
    int fa[maxn],de[maxn],deu[maxn],si;
    int seq[maxn*4],seqL,reseq[maxn];
    int st[maxn*4][21];
    inline void logSeq(int n){ seq[seqL++]=n; }
    inline void dfsBuild(int nw,int fax,int fad,int dex){
        de[nw]=fad,deu[nw]=dex,fa[nw]=fax;
        reseq[nw]=seqL;
        logSeq(nw);
        for(int i=h[nw],_;i;i=fy[i].n){
            _=fy[i].t;
            if(_==fa[nw]) continue;
            dfsBuild(_,nw,fad+1,dex+fy[i].v);
            logSeq(nw);
        }
    }
    inline int mindep(int a,int b){
        if(de[a]<de[b]) return a; else return b;
    }
    inline void genSt(){
        int t=l2e(seqL);
        for(int i=0;i<seqL;++i) st[i][0]=seq[i];
        for(int i=2,j=1;i<=seqL;i<<=1,++j){
            register int q=i>>1;
            for(int k=0,_=seqL-i;k<=_;++k){
                st[k][j]=mindep(st[k][j-1],st[k+q][j-1]);
            }
        }
    }
    inline int getmin(int a,int b){
        if(b<a) std::swap(a,b);
        int l=b-a+1;
        int le=l2e(l);
        int lk=1<<le;
        return mindep(st[a][le],st[b-lk+1][le]);
    }
    inline int LCA(int a,int b){
        return getmin(reseq[a],reseq[b]);
    }
    inline void build(int n){
        si=n;
        dfsBuild(1,0,0,0);genSt();
    }
    int impPoints[maxn],impL,blt[maxn];//important points, (length), belongs to
    int impDs[maxn],mxl,mxr,mxn;
    bool ft;
    inline int getMax(int l,int r){
        if(!ft){
            mxl=l,mxr=l-1;
            ft=1;
        } 
        while(mxl>l){
            --mxl;
            mxn=max(impDs[mxl],mxn);
        }
        while(mxr<r){
            ++mxr;
            mxn=max(impDs[mxr],mxn);
        }
        return mxn;
    }
    int resSes;
    inline void dfsResec(int nq,int fa){
        blt[nq]=resSes;
        for(int t=h[nq],_;t;t=fy[t].n){
            _=fy[t].t;
            if(_==fa) continue;
            dfsResec(_,nq);
        }
    }
    inline void resec(int n){
        resSes=n; blt[impPoints[n]]=n;
        for(int t=h[impPoints[n]],_;t;t=fy[t].n){
            _=fy[t].t;
            if(_==impPoints[n-1]) continue;
            if(_==impPoints[n+1]) continue;
            dfsResec(_,impPoints[n]);
        }
    }
} tr;
struct path{
    int f,t,p,len;
    path(int f=0,int t=0):f(f),t(t){}
    inline int lengthTot(){
        p=tr.LCA(f,t);
        return tr.deu[f]+tr.deu[t]-(tr.deu[p]<<1);
    }
    inline void rd(){
        scanf("%d%d",&f,&t);
        len=lengthTot();
    }
} paa[maxn];
inline bool cmp(const path& a,const path& b){
    return a.len>b.len;
}
int n,m,imps[maxn],sl;
inline void ps1(int n){
    ++tr.impL;
    tr.impPoints[tr.impL]=n;
}
inline void psl(int n){
    static int s=1;
    tr.impDs[s]=n;
    ++s;
}
inline void ps2(int n){
    ++sl;
    imps[sl]=n;
}
inline void getImpPo(){//get important points
    int tx=paa[1].f;
    while(tx!=paa[1].p){
        ps1(tx);
        psl(tr.deu[tx]-tr.deu[tr.fa[tx]]);
        tx=tr.fa[tx];
    }
    ps1(paa[1].p);
    tx=paa[1].t;
    while(tx!=paa[1].p){
        ps2(tx);
        tx=tr.fa[tx];
    }
    while(sl){
        tx=imps[sl];
        ps1(tx);
        psl(tr.deu[tx]-tr.deu[tr.fa[tx]]);
        --sl;
    }
    for(int i=1;i<=tr.impL;++i) tr.resec(i);
}
struct range{
    int l,r;
    inline range(int _l=0,int _r=0x7fffffff,bool testValid=1){
        l=_l,r=_r;
        if(testValid) if(l>r) std::swap(l,r);
    }
    inline range operator*(range b){ // intersect
        range p(l,r,0);
        if(b.l>l) p.l=b.l;
        if(b.r<r) p.r=b.r;
        return p;
    }
    inline bool hasRg(){
        return r>=l;
    }
} rgs[maxn];
int rgl;
inline void pushRange(range f){
    rgs[++rgl]=f;
}
inline range top(){
    return rgs[rgl];
}
inline bool same(range a,range b){
    return a.l==b.l && a.r==b.r;
}
inline void rt(){
    scanf("%d%d",&n,&m);
    for(int i=1,a,b,v;i<n;++i){
        scanf("%d%d%d",&a,&b,&v);
        ae(a,b,v); ae(b,a,v);
    }
    tr.build(n);
    for(int i=1;i<=m;++i) paa[i].rd();
    std::sort(paa+1,paa+m+1,cmp);
    getImpPo();
    for(int i=1;i<=m;++i) sww.push(paa[i].len);
    for(int i=1;i<=m;++i){
        pushRange(top()*range(tr.blt[paa[i].f],tr.blt[paa[i].t]));
    }
}
inline void tensen(int &a,int b){
    if(a>b) a=b;
}
int main(){
    freopen("transport.in","r",stdin);
    freopen("transport.out","w",stdout);
    rt();
    int i=m;
    int maxp=0x7fffffff;
    while(!rgs[i].hasRg()){ --i; }
    while(i){
        tensen(maxp,sww.qmaxe(i,tr.getMax(rgs[i].l,rgs[i].r)));
        --i;
    }
    printf("%d\n",maxp);
    return 0;
}

我没有写$O(n)$ LCA.

评论

wzj
扑通扑通跪下来
TA
请问sort不需要nlogn么？
Saber
然而你不还是有倍增。。明明可以写tarjan然后做到 n alpha n。。。好像窝也只会到这个地步
SCaffrey
%%%求保平安
Ciki
同想到O（n）算法但是考场没调出来而且没打暴力/握手

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

Server time: 2024-11-21 14:29:11