首页 > 其他分享 >杂题乱写 1

杂题乱写 1

时间：2023-12-04 19:59:18浏览次数：33  
标签：cnt 乱写 top int dfn MAXM inline 杂题

用树剖补完了普及组OJ所有LCA的题

Distance Queries 距离咨询

POJ-1986

  • 翻译:
    FJ有\(N（2\le N\le40000）\)个农场，标号\(1\)到\(N\)。\(M（2\le M\le 40000）\)条的不同的垂直或水平的道路连结着农场，道路的长度不超过\(1000\).这些农场的分布就像下面的地图一样，图中农场用\(F1\cdots F7\)表示：

image

每个农场最多能在东西南北四个方向连结\(4\)个不同的农场。此外，农场只处在道路的两端。道路不会交叉而且每对农场间有且仅有一条路径。邻居鲍伯要约翰来导航，但约翰丢了农场的地图，他只得从电脑的备份中修复率。每一条道路的信息如下：

从农场\(23\)往南经距离\(10\)到达农场\(17\)

从农场\(1\)往东经距离\(7\)到达农场\(17\)

\(\cdots\)

最近美国过度肥胖非常普遍。农夫约翰为了让他的奶牛多做运动，举办了奶牛马拉松。马拉松路线要尽量长。

奶牛们拒绝跑马拉松，因为她们悠闲的生活无法承受约翰选择的如此长的赛道。因此约翰决心找一条更合理的赛道。他打算咨询你。读入地图之后会有\(K\)个问题，每个问题包括\(2\)个整数，就是约翰感兴趣的\(2\)个农场的编号，请尽快算出这\(2\)个农场间的距离。

树剖板子题

先边权转点权,然后直接查询即可

CODE 
#include<bits/stdc++.h>
#define MAXM 0X66CCFF
#define int long long
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
int head[MAXM],NEXT[MAXM],TO[MAXM],cnt,tot,a[MAXM],Edge[MAXM];
struct node{
    int fa,dep,siz,son,top;
    int dfn,rnk;
}T[MAXM];
namespace Grape{
    inline void add(int u,int v,int w){
        NEXT[++tot]=head[u];
        TO[tot]=v;
        Edge[tot]=w;
        head[u]=tot;
    }
}
namespace ST{
    #define mid (l+r)/2
    #define lC q<<1
    #define rC q<<1|1
    struct St{
        long long l,r,siz;
        long long lazy,dat;
    }t[0x66ccff];
    void build(int q,int l,int r){
        t[q].l=l;
        t[q].r=r;
        t[q].siz=r-l+1;
        if(l==r){
            t[q].dat=a[T[l].rnk];
            return;
        }
        build(lC,l,mid);
        build(rC,mid+1,r);
        t[q].dat=t[lC].dat+t[rC].dat;
        #ifdef debug
            std::cout<<t[q].dat<<std::endl;
        #endif
    }
    void lazy(int q){
        t[lC].lazy+=t[q].lazy;
        t[lC].dat+=(t[lC].siz)*t[q].lazy;
        t[rC].lazy+=t[q].lazy;
        t[rC].dat+=(t[rC].siz)*t[q].lazy;
        t[q].lazy=0;
    }
    void change(int q,int l,int r,int v){
        if(t[q].l>r||t[q].r<l) return;
        if(t[q].l>=l && t[q].r<=r){
            t[q].lazy+=v;
            t[q].dat+=t[q].siz*v;
            return;
        }
        if(t[q].lazy!=0)
            lazy(q);
        change(lC,l,r,v);
        change(rC,l,r,v);
        t[q].dat=t[lC].dat+t[rC].dat;
    }
    long long asksum(int q,int l,int r){
        if(t[q].l>r || t[q].r<l) 
            return 0;
        if(t[q].l>=l && t[q].r<=r) 
            return t[q].dat;
        if(t[q].lazy!=0) 
            lazy(q);
        return asksum(lC,l,r)+asksum(rC,l,r); 
    }
}
namespace killTree{
    inline void Dfs1(int q){
        T[q].son=-1;
        T[q].siz=1;
        for(int j=head[q];j;j=NEXT[j]){
            if(T[TO[j]].dep) continue;
            a[TO[j]]=Edge[j];
            T[TO[j]].dep=T[q].dep+1;
            T[TO[j]].fa=q;
            Dfs1(TO[j]);
            T[q].siz+=T[TO[j]].siz;
            if((T[q].son==-1) || (T[TO[j]].siz>T[T[q].son].siz)) T[q].son=TO[j];
        }
    }
    inline void Dfs2(int q,int v){
        T[q].top=v;
        T[q].dfn=++cnt;
        T[cnt].rnk=q;
        if(T[q].son==-1)
            return;
        Dfs2(T[q].son,v);
        for(int j=head[q];j;j=NEXT[j]){
            if((TO[j]!=T[q].fa)&&(TO[j]!=T[q].son))
                Dfs2(TO[j],TO[j]);
        }
    }
    inline void TreeAdd(int x,int y,int val){
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) 
                std::swap(x,y);
            ST::change(1,T[T[x].top].dfn,T[x].dfn,val);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) 
            std::swap(x,y);
        ST::change(1,T[x].dfn+1,T[y].dfn,val);
    }
    inline int TreeSum(int x,int y){
        int ans=0;
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) std::swap(x,y);
            ans+=ST::asksum(1,T[T[x].top].dfn,T[x].dfn);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) std::swap(x,y);
        return ans+ST::asksum(1,T[x].dfn+1,T[y].dfn);
    }
    inline void AddTree(int x,int val){
        ST::change(1,T[x].dfn,T[x].dfn+T[x].siz-1,val);
    }
    inline int AskTree(int x){
        return ST::asksum(1,T[x].dfn,T[x].dfn+T[x].siz-1);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif 
    int N=read(),M=read(),R=1;
    for(int i=1;i<=M;i++){
        int u=read(),v=read(),w=read();
        char K8He=getchar();
        Grape::add(u,v,w);
        Grape::add(v,u,w);
    }
    T[R].dep=1;
    killTree::Dfs1(R);
    killTree::Dfs2(R,R);
    ST::build(1,1,N);
    int Q=read();
    for(int i=1;i<=Q;i++){
        int x=read(),y=read();
        std::cout<<killTree::TreeSum(x,y)<<std::endl;
    }
}

牧场旅行

\(n\)个被自然地编号为\(1\cdots n\)奶牛\(（1\le n\le 1000）\)正在同样被方便的编号为\(1..n\)的\(n\)个牧场中吃草。更加自然而方便的是，第\(i\)个奶牛就在第\(i\)个牧场中吃草。

其中的一些对牧场被总共的\(n-1\)条双向通道的一条连接。奶牛可以通过通道。第\(i\)条通道连接的两个牧场是\(A_i\)和\(B_i（1\le A_i\le N;1\le B_i\le N）\)其长度是\(L_i（1\le L_i\le 10000）\)。

通道只会连接两个不同的牧场，所以这些通道使得整个牧场构成了一棵树。

奶牛们是好交际的希望能够经常的访问别的奶牛。急切地，它们希望你能通过告诉它们\(Q（1\le Q\le 1000）\)对牧场的路径来帮助他们安排旅行。（这里将有\(Q\)个询问，\(p1,p2(1\le p1\le n；1\le p1\le n)\)）

这题树剖边权转点权板子题

CODE 


#include<bits/stdc++.h>
#define MAXM 0X66CCFF
#define int long long
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
int head[MAXM],NEXT[MAXM],TO[MAXM],cnt,tot,a[MAXM],Edge[MAXM];
struct node{
    int fa,dep,siz,son,top;
    int dfn,rnk;
}T[MAXM];
namespace Grape{
    inline void add(int u,int v,int w){
        NEXT[++tot]=head[u];
        TO[tot]=v;
        Edge[tot]=w;
        head[u]=tot;
    }
}
namespace ST{
    #define mid (l+r)/2
    #define lC q<<1
    #define rC q<<1|1
    struct St{
        long long l,r,siz;
        long long lazy,dat;
    }t[0x66ccff];
    void build(int q,int l,int r){
        t[q].l=l;
        t[q].r=r;
        t[q].siz=r-l+1;
        if(l==r){
            t[q].dat=a[T[l].rnk];
            return;
        }
        build(lC,l,mid);
        build(rC,mid+1,r);
        t[q].dat=t[lC].dat+t[rC].dat;
        #ifdef debug
            std::cout<<t[q].dat<<std::endl;
        #endif
    }
    void lazy(int q){
        t[lC].lazy+=t[q].lazy;
        t[lC].dat+=(t[lC].siz)*t[q].lazy;
        t[rC].lazy+=t[q].lazy;
        t[rC].dat+=(t[rC].siz)*t[q].lazy;
        t[q].lazy=0;
    }
    void change(int q,int l,int r,int v){
        if(t[q].l>r||t[q].r<l) return;
        if(t[q].l>=l && t[q].r<=r){
            t[q].lazy+=v;
            t[q].dat+=t[q].siz*v;
            return;
        }
        if(t[q].lazy!=0)
            lazy(q);
        change(lC,l,r,v);
        change(rC,l,r,v);
        t[q].dat=t[lC].dat+t[rC].dat;
    }
    long long asksum(int q,int l,int r){
        if(t[q].l>r || t[q].r<l) 
            return 0;
        if(t[q].l>=l && t[q].r<=r) 
            return t[q].dat;
        if(t[q].lazy!=0) 
            lazy(q);
        return asksum(lC,l,r)+asksum(rC,l,r); 
    }
}
namespace killTree{
    inline void Dfs1(int q){
        T[q].son=-1;
        T[q].siz=1;
        for(int j=head[q];j;j=NEXT[j]){
            if(T[TO[j]].dep) continue;
            a[TO[j]]=Edge[j];
            T[TO[j]].dep=T[q].dep+1;
            T[TO[j]].fa=q;
            Dfs1(TO[j]);
            T[q].siz+=T[TO[j]].siz;
            if((T[q].son==-1) || (T[TO[j]].siz>T[T[q].son].siz)) T[q].son=TO[j];
        }
    }
    inline void Dfs2(int q,int v){
        T[q].top=v;
        T[q].dfn=++cnt;
        T[cnt].rnk=q;
        if(T[q].son==-1)
            return;
        Dfs2(T[q].son,v);
        for(int j=head[q];j;j=NEXT[j]){
            if((TO[j]!=T[q].fa)&&(TO[j]!=T[q].son))
                Dfs2(TO[j],TO[j]);
        }
    }
    inline void TreeAdd(int x,int y,int val){
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) 
                std::swap(x,y);
            ST::change(1,T[T[x].top].dfn,T[x].dfn,val);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) 
            std::swap(x,y);
        ST::change(1,T[x].dfn+1,T[y].dfn,val);
    }
    inline int TreeSum(int x,int y){
        int ans=0;
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) std::swap(x,y);
            ans+=ST::asksum(1,T[T[x].top].dfn,T[x].dfn);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) std::swap(x,y);
        return ans+ST::asksum(1,T[x].dfn+1,T[y].dfn);
    }
    inline void AddTree(int x,int val){
        ST::change(1,T[x].dfn,T[x].dfn+T[x].siz-1,val);
    }
    inline int AskTree(int x){
        return ST::asksum(1,T[x].dfn,T[x].dfn+T[x].siz-1);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif 
    int N=read(),Q=read(),R=1;
    for(int i=1;i<N;i++){
        int u=read(),v=read(),w=read();
        Grape::add(u,v,w);
        Grape::add(v,u,w);
    }
    T[R].dep=1;
    killTree::Dfs1(R);
    killTree::Dfs2(R,R);
    ST::build(1,1,N);
    std::cerr<<"Furry";
    for(int i=1;i<=Q;i++){
        int x=read(),y=read();
        std::cout<<killTree::TreeSum(x,y)<<std::endl;
    }
}

货车运输

\(A\) 国有\(n\)座城市，编号从\(1\)到\(n\)，城市之间有\(m\)条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有\(q\)辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

最大生成树+树剖板子题

记得边权转点权

CODE 
#include<bits/stdc++.h>
#define MAXM 0X66CCFF
#define int long long
#define INF 0X66CCFF0712
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
int head[MAXM],NEXT[MAXM],TO[MAXM],cnt,tot,a[MAXM],Edge[MAXM],f[MAXM],N,M;
struct node{
    int fa,dep,siz,son,top;
    int dfn,rnk;
}T[MAXM];
namespace Grape{
    inline void add(int u,int v,int w){
        NEXT[++tot]=head[u];
        TO[tot]=v;
        Edge[tot]=w;
        head[u]=tot;
    }
    struct EDGE{
        int x,y,w;
    }e[MAXM];
    inline bool cmp(EDGE a,EDGE b){
        return a.w>b.w;
    }  
    int find(int x){
        if(x!=f[x])
            f[x]=find(f[x]);
        return f[x];
    }           
    inline void Kruskal(){
        for(int i=1;i<=N;i++)
            f[i]=i;
        std::sort(e+1,e+M+1,cmp);
        int ans=0;
        for(int i=1;i<=M;i++){
            int aa=find(e[i].x),b=find(e[i].y);
            if(aa!=b){
                f[aa]=b;ans++;
                add(e[i].x,e[i].y,e[i].w);
                add(e[i].y,e[i].x,e[i].w);
            }
        }
    }
}
namespace ST{
    #define mid (l+r)/2
    #define lC q<<1
    #define rC q<<1|1
    struct St{
        long long l,r,siz;
        long long lazy,dat;
    }t[0x66ccff];
    void build(int q,int l,int r){
        t[q].l=l;
        t[q].r=r;
        t[q].siz=r-l+1;
        if(l==r){
            t[q].dat=a[T[l].rnk];
            return;
        }
        build(lC,l,mid);
        build(rC,mid+1,r);
        t[q].dat=std::min(t[lC].dat,t[rC].dat);
        #ifdef debug
            std::cout<<t[q].dat<<std::endl;
        #endif
    }
    void lazy(int q){
        t[lC].lazy+=t[q].lazy;
        t[lC].dat+=t[q].lazy;
        t[rC].lazy+=t[q].lazy;
        t[rC].dat+=t[q].lazy;
        t[q].lazy=0;
    }
    void change(int q,int l,int r,int v){
        if(t[q].l>r||t[q].r<l) return;
        if(t[q].l>=l && t[q].r<=r){
            t[q].lazy+=v;
            t[q].dat+=v;
            return;
        }
        if(t[q].lazy!=0)
            lazy(q);
        change(lC,l,r,v);
        change(rC,l,r,v);
        t[q].dat=std::min(t[lC].dat,t[rC].dat);
    }
    long long askmin(int q,int l,int r){
        if(t[q].l>r || t[q].r<l) 
            return INF;
        if(t[q].l>=l && t[q].r<=r) 
            return t[q].dat;
        if(t[q].lazy!=0) 
            lazy(q);
        return std::min(askmin(lC,l,r),askmin(rC,l,r)); 
    }
}
namespace killTree{
    inline void Dfs1(int q){
        T[q].son=-1;
        T[q].siz=1;
        for(int j=head[q];j;j=NEXT[j]){
            if(T[TO[j]].dep) continue;
            a[TO[j]]=Edge[j];
            T[TO[j]].dep=T[q].dep+1;
            T[TO[j]].fa=q;
            Dfs1(TO[j]);
            T[q].siz+=T[TO[j]].siz;
            if((T[q].son==-1) || (T[TO[j]].siz>T[T[q].son].siz)) T[q].son=TO[j];
        }
    }
    inline void Dfs2(int q,int v){
        T[q].top=v;
        T[q].dfn=++cnt;
        T[cnt].rnk=q;
        if(T[q].son==-1)
            return;
        Dfs2(T[q].son,v);
        for(int j=head[q];j;j=NEXT[j]){
            if((TO[j]!=T[q].fa)&&(TO[j]!=T[q].son))
                Dfs2(TO[j],TO[j]);
        }
    }
    inline void TreeAdd(int x,int y,int val){
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) 
                std::swap(x,y);
            ST::change(1,T[T[x].top].dfn,T[x].dfn,val);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) 
            std::swap(x,y);
        ST::change(1,T[x].dfn+1,T[y].dfn,val);
    }
    inline int TreeSum(int x,int y){
        int ans=INF;
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) std::swap(x,y);
            ans=std::min(ans,ST::askmin(1,T[T[x].top].dfn,T[x].dfn));
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) std::swap(x,y);
        return std::min(ans,ST::askmin(1,T[x].dfn+1,T[y].dfn));
    }
    inline void AddTree(int x,int val){
        ST::change(1,T[x].dfn,T[x].dfn+T[x].siz-1,val);
    }
    inline int AskTree(int x){
        return ST::askmin(1,T[x].dfn,T[x].dfn+T[x].siz-1);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif 
    N=read(),M=read();
    int Q,R=1;
    for(int i=1;i<=M;i++){
        Grape::e[i].x=read(),
        Grape::e[i].y=read(),
        Grape::e[i].w=read();
    }
    Grape::Kruskal();
    T[R].dep=1;
    killTree::Dfs1(R);
    killTree::Dfs2(R,R);
    ST::build(1,1,N);
    std::cerr<<"Furry";
    Q=read();
    for(int i=1;i<=Q;i++){
        int x=read(),y=read();
        if(killTree::TreeSum(x,y)==0X66CCFF0712||killTree::TreeSum(x,y)==0){std::cout<<-1<<std::endl;continue;}
        std::cout<<killTree::TreeSum(x,y)<<std::endl;
    }
}

星际导航

sideman做好了回到Gliese 星球的硬件准备，但是sideman的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有N 个顶点和M 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。

sideman 现在想把危险程度降到最小，具体地来说，就是对于若干个询问(A, B)，sideman 想知道从顶点A 航行到顶点B 所经过的最危险的边的危险程度值最小可能是多少。作为sideman 的同学，你们要帮助sideman 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。

最小生成树+树链剖分板子题

这题直接做就行，不过给出的数据有森林然后不判会WA我服了

CODE 


#include<bits/stdc++.h>
#define MAXM 0X66CCFF
#define int long long
#define INF 0X66CCFF0712
namespace IO{
    inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
    inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
    inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
int head[MAXM],NEXT[MAXM],TO[MAXM],cnt,tot,a[MAXM],Edge[MAXM],f[MAXM],N,M;
struct node{
    int fa,dep,siz,son,top;
    int dfn,rnk;
}T[MAXM];
namespace Grape{
    inline void add(int u,int v,int w){
        NEXT[++tot]=head[u];
        TO[tot]=v;
        Edge[tot]=w;
        head[u]=tot;
    }
    struct EDGE{
        int x,y,w;
    }e[MAXM];
    inline bool cmp(EDGE a,EDGE b){
        return a.w<b.w;
    }  
    int find(int x){
        if(x!=f[x])
            f[x]=find(f[x]);
        return f[x];
    }           
    inline void Kruskal(){
        for(int i=1;i<=N;i++)
            f[i]=i;
        std::sort(e+1,e+M+1,cmp);
        int ans=0;
        for(int i=1;i<=M;i++){
            int aa=find(e[i].x),b=find(e[i].y);
            if(aa!=b){
                f[aa]=b;ans++;
                add(e[i].x,e[i].y,e[i].w);
                add(e[i].y,e[i].x,e[i].w);
            }
        }
    }
}
namespace ST{
    #define mid (l+r)/2
    #define lC q<<1
    #define rC q<<1|1
    struct St{
        long long l,r,siz;
        long long lazy,dat;
    }t[0x66ccff];
    void build(int q,int l,int r){
        t[q].l=l;
        t[q].r=r;
        t[q].siz=r-l+1;
        if(l==r){
            t[q].dat=a[T[l].rnk];
            return;
        }
        build(lC,l,mid);
        build(rC,mid+1,r);
        t[q].dat=std::max(t[lC].dat,t[rC].dat);
        #ifdef debug
            std::cout<<t[q].dat<<std::endl;
        #endif
    }
    void lazy(int q){
        t[lC].lazy+=t[q].lazy;
        t[lC].dat+=t[q].lazy;
        t[rC].lazy+=t[q].lazy;
        t[rC].dat+=t[q].lazy;
        t[q].lazy=0;
    }
    void change(int q,int l,int r,int v){
        if(t[q].l>r||t[q].r<l) return;
        if(t[q].l>=l && t[q].r<=r){
            t[q].lazy+=v;
            t[q].dat+=v;
            return;
        }
        if(t[q].lazy!=0)
            lazy(q);
        change(lC,l,r,v);
        change(rC,l,r,v);
        t[q].dat=std::max(t[lC].dat,t[rC].dat);
    }
    long long askmax(int q,int l,int r){
        if(t[q].l>r || t[q].r<l) 
            return 0;
        if(t[q].l>=l && t[q].r<=r) 
            return t[q].dat;
        if(t[q].lazy!=0) 
            lazy(q);
        return std::max(askmax(lC,l,r),askmax(rC,l,r)); 
    }
}
namespace killTree{
    inline void Dfs1(int q){
        T[q].son=-1;
        T[q].siz=1;
        for(int j=head[q];j;j=NEXT[j]){
            if(T[TO[j]].dep) continue;
            a[TO[j]]=Edge[j];
            T[TO[j]].dep=T[q].dep+1;
            T[TO[j]].fa=q;
            Dfs1(TO[j]);
            T[q].siz+=T[TO[j]].siz;
            if((T[q].son==-1) || (T[TO[j]].siz>T[T[q].son].siz)) T[q].son=TO[j];
        }
    }
    inline void Dfs2(int q,int v){
        T[q].top=v;
        T[q].dfn=++cnt;
        T[cnt].rnk=q;
        if(T[q].son==-1)
            return;
        Dfs2(T[q].son,v);
        for(int j=head[q];j;j=NEXT[j]){
            if((TO[j]!=T[q].fa)&&(TO[j]!=T[q].son))
                Dfs2(TO[j],TO[j]);
        }
    }
    inline void TreeAdd(int x,int y,int val){
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) 
                std::swap(x,y);
            ST::change(1,T[T[x].top].dfn,T[x].dfn,val);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) 
            std::swap(x,y);
        ST::change(1,T[x].dfn+1,T[y].dfn,val);
    }
    inline int TreeSum(int x,int y){
        int ans=0;
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) std::swap(x,y);
            ans=std::max(ans,ST::askmax(1,T[T[x].top].dfn,T[x].dfn));
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) std::swap(x,y);
        return std::max(ans,ST::askmax(1,T[x].dfn+1,T[y].dfn));
    }
    inline void AddTree(int x,int val){
        ST::change(1,T[x].dfn,T[x].dfn+T[x].siz-1,val);
    }
    inline int AskTree(int x){
        return ST::askmax(1,T[x].dfn,T[x].dfn+T[x].siz-1);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif 
    N=read(),M=read();
    int Q,R=1;
    for(int i=1;i<=M;i++){
        Grape::e[i].x=read(),
        Grape::e[i].y=read(),
        Grape::e[i].w=read();
    }
    Grape::Kruskal();
    T[R].dep=1;
    killTree::Dfs1(R);
    killTree::Dfs2(R,R);
    ST::build(1,1,N);
    std::cerr<<"Furry";
    Q=read();
    for(int i=1;i<=Q;i++){
        int x=read(),y=read();
        if(killTree::TreeSum(x,y)==0||Grape::find(x)!=Grape::find(y)){std::cout<<"impossible"<<std::endl;continue;}
        std::cout<<killTree::TreeSum(x,y)<<std::endl;
    }
}

标签：cnt,乱写,top,int,dfn,MAXM,inline,杂题
From： https://www.cnblogs.com/LuoTianYi66ccff/p/17875775.html

相关文章

  • 网络流杂题
    一道一道记太浪费文章篇数了。先记几种dinic的复杂度。一般网络：\(O(n^2m)\)各边容量为\(1\)的网络：\(O(m\min\{m^{\frac{1}{2}},n^{\frac{2}{3}}\})\)二分图：\(O(m\sqrtn)\)更详细的分析。最大流UVA10735混合图的欧拉回路存在欧拉回路的判断条件：每个点出度=入度......
  • 【杂题乱写】2023-11 #2
    ARC147CFindthemaximumLandtheminimumRtobemLandmRrespectively.IfmL<=mRholds,wecansetevery\(x_i\)tobemLandthecontributionwillbe0.Otherwisewe'dgreedilyset\(R_{\arg\minR}=mR\)and\(L_{\arg\maxL}=mL\).All......
  • 「杂题乱刷」CF1585B
    原题链接CF1585BArrayEversion题目简述现在有一个长度为\(n\)的序列\(a\)，每次操作将\(a\)中不大于序列\(a\)中最后一个数的元素按照在\(a\)序列中的顺序放入\(b\)序列中，大于序列\(a\)中最后一个数的元素同样按照在\(a\)中的顺序放入\(c\)序列中，然后再将\(c......
  • 「杂题乱刷」CF468A
    原题链接CF468A24Game题目简述现在有一个序列\(n\)包含\(n\)个整数\(1\simn\)，如果我们能经过加减乘三种操作让这个序列只剩下\(24\)，如果可以，输出YES并给出构造方案，否则输出NO。解题思路首先不难看出，如果\(n\)小于\(4\)的话，那么是一定不能构造出方案的，因为无......
  • 「杂题乱刷」洛谷P9515
    原题链接P9515「JOC-1A」限时签到题意简述有一条公路上有\(n\)个商店，每个商店分别在不同的时刻开放，求如何在\(t\)时刻之前到达\(f\)点并且到达最多开放的商店的数量，特别的，一个时刻只能走一格。解题思路这一道题是一道贪心题。首先，因为要在\(t\)时刻之前到达\(f\)......
  • 「杂题乱刷」CF283A
    原题链接CF283ACowsandSequence题目简述给定一个初始为空的序列\(a\)，并给出\(3\)种操作方式：将\(a_1\sima_x\)均加上\(y\)；将\(a\)序列末尾增加一个正整数\(x\)；将\(a\)序列的最后一个数字给去掉；现在要求你求出进行每一次操作后的序列\(a\)的所有数......
  • 「杂题乱刷」洛谷P9253
    题目链接P9253[PA2022]Ornitolog2题目简述给定一个音高序列，输出最少要修改多少整数才能使这个序列成为交替鹡鸰鸟鸣的音高序列。题意分析操作后的音高序列总共有\(2\)种可能：音量由高变低再由低变高；音量由低变高再由高变低。又因为大小范围是\(10^4\times5......
  • 10月杂题
    还是得写写杂题，初三赛季说明这对我是buff啊。这次CSP-S再次检验王者是超级debuff！！！1.P7830[CCO2021]ThroughAnotherMazeDarkly感受一下，每次从根开始绕一圈回去，这个圈会越来越大，直到大小变成\(n-1\)。考虑求出每个边在最后一个圈内入和出的时间（就是欧拉序），你会发现每......
  • 11月杂题
    1.10.30D/qoj6794SequencetoSequence先观察到我们一定是先减后加。因为对于一个数+1-1一定不会改变，但-1+1就会有改变。那对于相邻的+1-1操作，如果不交就直接交换；否则把相交的部分直接删掉，那要么删成两个+1，要么成两个-1，要么是不交的+1-1。如果我们指定一个数减......
  • 9月杂题
    为什么19号了才开始写杂题1.ZJOI2018胖考虑一个新增边能松哪些点。它会被其它新增边影响。感受一下，松的范围一定是一个区间。如果\(|x-x_i|>|x-x_j|\)且\(b_i+|s_x-s_{x_i}|>b_j+|s_x-s_{x_j}|\)，\(i\)就松不到\(j\)。二分边界，RMQ判断即可。以左端点为例，\([mid,i]\)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99