【线段树分治】Dash Speed

代码的美妙
#include <bits/stdc++.h>

%:pragma GCC optimize(3)

using namespace std;

const int maxn=7e4+10;

int n,m;

int ans[maxn];

pair<int,int> tree[maxn];

struct Edge{

    int from,to,nxt;

}e[maxn<<1];

inline int read(){

    int x=0;bool fopt=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=0;

    for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;

    return fopt?x:-x;

}

int head[maxn],cnt;

inline void add(int u,int v){

    e[++cnt].from=u;

    e[cnt].to=v;

    e[cnt].nxt=head[u];

    head[u]=cnt;

}

namespace LinkCut{

    int fa[maxn],dep[maxn],siz[maxn],son[maxn],dis[maxn];

    void dfs1(int u){

        dep[u]=dep[fa[u]]+1;siz[u]=1;

        for(int i=head[u];i;i=e[i].nxt){

            int v=e[i].to;

            if(v==fa[u])continue;

            fa[v]=u;dfs1(v);

            siz[u]+=siz[v];

            if(!son[u]||siz[v]>siz[son[u]])son[u]=v;

        }

    }

    int top[maxn];

    void dfs2(int u,int t){

        top[u]=t;

        for(int i=head[u];i;i=e[i].nxt){

            int v=e[i].to;

            if(v==fa[u])continue;

            dfs2(v,v==son[u]?t:v);

        }

    }

    inline int lca(int u,int v){

        while(top[u]!=top[v]){

            if(dep[top[u]]<dep[top[v]])swap(u,v);

            u=fa[top[u]];

        }

        return dep[u]<dep[v]?u:v;

    }

    inline int getdis(int u,int v){

        int lcam=lca(u,v);

        return dep[u]+dep[v]-(dep[lcam]<<1);

    }

}

using namespace LinkCut;

namespace DSU{

    int f[maxn],size[maxn];

    int t=0;

    struct Node{

        int x,y,v;

        pair<int,int> p;

    }sta[maxn];

    inline void Init(){

        for(int i=1;i<=n;i++)

            f[i]=i;

    }

    int Find(int x){

        return x==f[x]?x:Find(f[x]);

    }

    inline void del(int x){

        while(x<t){

            Node u=sta[t--];

            size[u.x]-=u.v;

            f[u.y]=u.y;

            tree[u.x]=u.p;

        }

    }

}

using namespace DSU;

namespace SEG{

#define lson (rt<<1)

#define rson (rt<<1|1)

    vector<pair<int,int> > pos[maxn<<2];

    inline pair<int,int> pushup(pair<int,int> A,pair<int,int> B,int &flag){

        int p[4]={A.first,A.second,B.first,B.second};

            int Max=-1;pair<int,int> res;

            for(int i=0;i<4;i++)

                for(int j=i+1;j<4;j++){

                    int w=getdis(p[i],p[j]);

                    if(w>Max){

                        Max=w;res=make_pair(p[i],p[j]);

                    }

                }

        flag=max(Max,flag);

        return res;

    }

    inline void build(){

        for(int i=1;i<=n;i++)

            tree[i]=make_pair(i,i);

    }

    void modify(int rt,int l,int r,int s,int t,int u,int v){

        if(r<s||t<l)return;

        if(s<=l&&r<=t)return pos[rt].push_back(make_pair(u,v)),void();

        int mid=(l+r)>>1;

        modify(lson,l,mid,s,t,u,v);

        modify(rson,mid+1,r,s,t,u,v);

    }

    inline void Merge(int x,int y,int &res){

        x=Find(x);y=Find(y);

        pair<int,int> temp=pushup(tree[x],tree[y],res);

        if(size[x]<size[y])swap(x,y);

        sta[++t]=(Node){x,y,0,tree[x]};

        if(size[x]==size[y]){

            size[x]++;sta[t].v=1;

        }

        f[y]=x;tree[x]=temp;

    }

    void Solve(int rt,int l,int r,int res){

        int now=t;

        for(int i=0;i<pos[rt].size();i++)

            Merge(pos[rt][i].first,pos[rt][i].second,res);

        if(l==r){

            ans[l]=res;del(now);return;

        }

        int mid=(l+r)>>1;

        Solve(lson,l,mid,res);

        Solve(rson,mid+1,r,res);

        del(now);

    }

#undef lson

#undef rson

}

using namespace SEG;

int main(){

#ifndef LOCAL

    freopen("ds.in","r",stdin);

    freopen("ds.out","w",stdout);

#endif

    n=read();m=read();

    for(int i=1;i<n;i++){

        int u=read(),v=read(),l=read(),r=read();

        add(u,v);add(v,u);

        modify(1,1,n,l,r,u,v);

    }

    dfs1(1);dfs2(1,1);

    Init();build();

    Solve(1,1,n,0);

    while(m--){

        int q=read();

        printf("%d\n",ans[q]);

    }

    return 0;

}
巴特西

【线段树分治】Dash Speed

最新文章

热门文章
