您的位置: 首页  >  IT文章  >  牛客练习赛67 F-牛妹的苹果树（树上最远点对/区间带权直径-线段树+LCA）

牛客练习赛67 F-牛妹的苹果树（树上最远点对/区间带权直径-线段树+LCA）

分类: IT文章 • 2022-04-26 22:07:42

题目链接：https://ac.nowcoder.com/acm/contest/6885/F
CSDN食用链接：https://blog.csdn.net/qq_43906000/article/details/108020137

题目描述

牛妹种了一棵苹果树。

这棵苹果树有n个节点，n-1条边，每一条边都有一个权值(w_i)我们定义：这棵树上的两点之间距离(dist(u,v))为它们简单路径上所有边的权值和。

现在，牛妹想给你q次询问，每次询问一个区间[l,r]，求(max(dist(u,v)),lle ule vle r)。

输入描述:
第一行，读入n和q。

接下来n-1行，每行读入u，v和w，表示一条边。

接下来q行，每行读入l和r，表示一组询问。

输出描述:
对于每一组询问，输出对应的最大距离值。

输入
3 3
1 2 20
2 3 40
1 1
1 3
1 2
输出
0
60
20

说明
第一组询问，最长距离是节点1到节点1，距离为0；

第二组询问，最长距离是节点1到节点3，距离为20+40=60；

第三组询问，最长距离是节点1到节点2，距离为20.

备注:
数据保证(1le n,qle 300000,1le w_ile 10^9,)

emmm。。。怎么说呢，这题和51nod1766撞了，只不过这题的(w_i)稍微调大了点，不过问题不大，稍微改改还是能过的，所以如果知道这个原题的话。。这场AK就似乎挺简单的了。。。只不过注意一下卡常就行了。

以下是AC板子：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read(){
    int x=0;
    char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
const int N=300005;
const ll INF=4e18;
struct Gragh{
    static const int M=N*2;
    int cnt,y[M],z[M],nxt[M],fst[N];
    inline void clear(){
        cnt=1;
        memset(fst,0,sizeof fst);
    }
    inline void add(int a,int b,int c){
        y[++cnt]=b,z[cnt]=c,nxt[cnt]=fst[a],fst[a]=cnt;
    }
}g;
#define list pupu
int n;
int fa[N][20],depth[N],Log[N*2];
ll ld[N];
int ST[N*2][20],list[N*2],dfn=0,in[N],out[N];
void dfs(int x,int pre,int d,ll dd){
    depth[x]=d,fa[x][0]=pre,ld[x]=dd;
    list[in[x]=++dfn]=x;
    for (int i=1;i<20;i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for (int i=g.fst[x];i;i=g.nxt[i])
        if (g.y[i]!=pre){
            dfs(g.y[i],x,d+1,dd+g.z[i]);
            list[++dfn]=x;
        }
    out[x]=dfn;
}
inline int spmax(int a,int b){
    return depth[a]<depth[b]?a:b;
}
void prework(){
    for (int i=1;i<=dfn;i++){
        ST[i][0]=list[i];
        for (int j=1;j<20;j++){
            ST[i][j]=ST[i][j-1];
            if (i-(1<<(j-1))>0)
                ST[i][j]=spmax(ST[i][j-1],ST[i-(1<<(j-1))][j-1]);
        }
    }
}
inline int query(int L,int R){
    int d=Log[R-L+1];
    return spmax(ST[L+(1<<d)-1][d],ST[R][d]);
}
inline int LCA(int x,int y){
    return query(min(in[x],in[y]),max(in[x],in[y]));
}
#define fi first
#define se second
#define pii pair <ll,ll>
pii t[N<<2];
inline ll dis(int x,int y){
    if (!~x&&!~y)
        return -2LL*INF;
    if (!~x||!~y)
        return -INF;
    return ld[x]+ld[y]-2LL*ld[LCA(x,y)];
}
inline pii Merge(pii a,pii b){
    pii res=dis(a.fi,a.se)>dis(b.fi,b.se)?a:b;
    if (dis(a.fi,b.fi)>dis(res.fi,res.se))res=make_pair(a.fi,b.fi);
    if (dis(a.fi,b.se)>dis(res.fi,res.se))res=make_pair(a.fi,b.se);
    if (dis(a.se,b.fi)>dis(res.fi,res.se))res=make_pair(a.se,b.fi);
    if (dis(a.se,b.se)>dis(res.fi,res.se))res=make_pair(a.se,b.se);
    return res;
}
void build(int rt,int L,int R){
    if (L==R){
        t[rt]=make_pair(L,-1);
        return;
    }
    int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
    build(ls,L,mid);
    build(rs,mid+1,R);
    t[rt]=Merge(t[ls],t[rs]);
}
pii query(int rt,int L,int R,int xL,int xR){
    if (R<xL||L>xR)
        return make_pair(-1,-1);
    if (xL<=L&&R<=xR)
        return t[rt];
    int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
    return Merge(query(ls,L,mid,xL,xR),query(rs,mid+1,R,xL,xR));
}
int main(){
    n=read();
    int m=read();
    g.clear();
    for (int i=1;i<n;i++){
        int a=read(),b=read(),c=read();
        g.add(a,b,c);
        g.add(b,a,c);
    }
    dfs(1,0,0,0);
    Log[1]=0;
    for (int i=2;i<=dfn;i++)
        Log[i]=Log[i>>1]+1;
    prework();
    build(1,1,n);
    while (m--){
        int a=read(),b=read();
        if (a==b) {printf("0
"); continue;}
        pii x=query(1,1,n,a,b);
        printf("%lld
",dis(x.fi,x.se));
    }
    return 0;
}

相关推荐