51nod

分析

考虑建立一棵线段树,每个节点维护编号在 $[l,r]$ 内的节点中选两点距离的最大值。

考虑合并,容易发现只会有六种可能的情况即四个端点两两组合。

查询时求出每个区间对应的两个端点,四种情况取 $\max$ 即可。

如果常数大的话写树剖容易被卡。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q;

struct edge { int v,w,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

int dep[N],dis[N],lg[N<<1],pos[N],st[18][N<<1],tot=0;
inline void dfs(int u,int fa) {
    st[0][++tot]=u,pos[u]=tot,dep[u]=dep[fa]+1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w; if (v==fa) continue;
        dis[v]=dis[u]+w,dfs(v,u),st[0][++tot]=u;
    }
}
inline int cmp(int a,int b) { return dep[a]<dep[b]?a:b; }
inline void init_rmq() {
    for (re int i=2;i<=tot;++i) lg[i]=lg[i>>1]+1;
    for (re int i=1;i<18;++i)
        for (re int j=1;j+(1<<i)-1<=tot;++j)
            st[i][j]=cmp(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
inline int getdis(int u,int v) {
    if (pos[u]>pos[v]) swap(u,v);
    int t=lg[pos[v]-pos[u]+1];
    int lca=cmp(st[t][pos[u]],st[t][pos[v]-(1<<t)+1]);
    return dis[u]+dis[v]-(dis[lca]<<1);
}

#define ls (o<<1)
#define rs (o<<1|1)
struct node { int l,r; } t[N<<2];
node operator +(node a,node b) {
    int p[4]={a.l,a.r,b.l,b.r},mx=-1; node res;
    for (re int i=0;i<4;++i)
        for (re int j=i+1;j<4;++j)
            if (getdis(p[i],p[j])>mx)
                mx=getdis(p[i],p[j]),res=(node){p[i],p[j]};
    return res;
}
inline void pushup(int o) { t[o]=t[ls]+t[rs]; }
inline void build(int o,int l,int r) {
    if (l==r) { t[o].l=t[o].r=l; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
inline node query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return t[o];
    int mid=(l+r)>>1;
    if (qr<=mid) return query(ls,l,mid,ql,qr);
    else if (ql>mid) return query(rs,mid+1,r,ql,qr);
    else return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr);
}
#undef ls
#undef rs

int main() {
    n=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w),addEdge(v,u,w);
    }
    dfs(1,0),init_rmq(); build(1,1,n);
    Q=read();
    while (Q--) {
        int a=read(),b=read(),c=read(),d=read();
        node x=query(1,1,n,a,b),y=query(1,1,n,c,d);
        printf("%d\n",max(max(getdis(x.l,y.l),getdis(x.l,y.r)),
                          max(getdis(x.r,y.l),getdis(x.r,y.r))));
    }
    return 0;
}
最后修改:2020 年 03 月 14 日 04 : 59 PM