hdu 6010 路径交(lca + 线段树)

题意：

给出一棵大小为\(n\)的树和\(m\)条路径，求第\(L\)条路径到第\(R\)条路径的交的路径的长度

思路:

本题的关键就是求路径交

假设存在两条路径(a,b),(c,d),那它们的交是怎样的呢

画图看看,分三种情况

1、路径不存在交集

2、(c,d)交(a,b)路径的一边(由lca(a,b)将路径划分成两部分,假设这里交在a的一侧)

3、(c,d)交(a,b)路径的两边

可以看出路径交若存在，这其两端点一定在lca(a,c),lca(a,d),lca(b,c),lca(b,d)中取到，

而且是取深度最大的两点，如果这两点相同，那么显然路径只交于一点了

这里是问边的交集

如果是求的点的交集，还需要判断一下点是否在路径上，可以用距离来判断

然后剩下的来就是简单的线段树求区间的合并了

#include<bits/stdc++.h>

#define LL long long

#define P pair<int,int>

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define ls rt<<1

#define rs (rt<<1|1)

using namespace std;

int read(){

    int x = 0;

    char c = getchar();

    while(c < '0' || c > '9') c = getchar();

    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();

    return x;

}

const int N = 5e5 + 10;

int n,m;

int pre[N];

vector<P> G[N];

int dep[N],dis[N];

int fa[N][25];

int dp[N][25];

int ver[2 * N],tot;

int first[N],R[2 * N];

void dfs(int u,int f,int d,int dw){

    dep[u] = d;

    dis[u] = dw;

    fa[u][0] = f;

    ver[++tot] = u;

    first[u] = tot,R[tot] = d;

   // for(int i = 1;i <= 20;i++) fa[u][i] = fa[fa[u][i-1]][i-1];

    for(int i = 0;i < G[u].size();i++){

        if(G[u][i].first != f) {

                dfs(G[u][i].first,u,d + 1,dw + G[u][i].second);

                ver[++tot] = u;

                R[tot] = d;

        }

    }

}

void ST(int n){

    for(int i = 1;i <= n;i++) dp[i][0] = i;

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

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

            int a=  dp[i][j-1],b = dp[i+(1<<(j-1))][j-1];

            dp[i][j] = R[a] < R[b]?a:b;

        }

    }

}

int RMQ(int l,int r){

    int k = pre[r - l + 1];

    int a = dp[l][k],b = dp[r-(1<<k)+1][k];

    return R[a] < R[b]?a:b;

}

int lca(int u,int v){

    int x = first[u],y = first[v];

    if(x > y) swap(x,y);

    int res = RMQ(x,y);

    return ver[res];

}/*

int lca(int u,int v){

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

    int d = dep[u] - dep[v];

    for(int i = 20;i >= 0 && u != v;i--) if(d & (1<<i)) u = fa[u][i];

    if(u == v) return u;

    for(int i = 20;i >= 0;i--) if(fa[u][i] != fa[v][i]) u = fa[u][i],v = fa[v][i];

    return fa[u][0];

}*/

int getdis(int u,int v){

    return dis[u] + dis[v] - 2 * dis[lca(u,v)];

}

void sw(int &x,int &y){

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

}

struct Line{

    int u,v,uv;

    Line(int u,int v,int uv):u(u),v(v),uv(uv){};

    Line(){};

    Line operator+(const Line &rhs)const{

        if(uv == 0) return rhs;

        if(rhs.uv == 0)return *this;

        if(uv == -1 || rhs.uv == -1) return Line(0,0,-1);

        Line ans;

        int lu = lca(u,rhs.u), lv = lca(u,rhs.v);

        int ru = lca(v,rhs.u), rv = lca(v,rhs.v);

        sw(lu,lv);sw(ru,rv);

        if(dep[lu] > dep[ru]){

            ans.u = lu;

            ans.v = dep[ru] > dep[lv]?ru:lv;

        }else {

            ans.u = ru;

            ans.v = dep[lu] > dep[rv]?lu:rv;

        }

        if(ans.u == ans.v) return Line(0,0,-1);

        ans.uv = lca(ans.u,ans.v);

        return ans;

    }

}s[N << 2];

void build(int l,int r,int rt){

    if(l == r){

        s[rt].u = read();

        s[rt].v = read();

        s[rt].uv = lca(s[rt].u,s[rt].v);

        return ;

    }

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

    build(l,m,rt<<1);

    build(m+1,r,rt<<1|1);

    s[rt] = s[rt<<1] + s[rt<<1|1];

}

Line query(int L,int R,int l,int r,int rt){

    if(L <= l && R >= r) return s[rt];

    int m = l + r >>1;

    Line ans = Line(0,0,0);

    if(L <= m) ans = ans + query(L,R,l,m,rt<<1);

    if(R > m) ans = ans + query(L,R,m+1,r,rt<<1|1);

    return ans;

}

int main(){

    for(int i = 1;i < N ;i++) pre[i] = log2(i);

    int u,v,w;

    while(scanf("%d",&n)==1){

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

            u = read(),v = read(), w = read();

            G[u].push_back(P(v,w));

            G[v].push_back(P(u,w));

        }

        dfs(1,-1,0,0);

        ST(2 * n - 1);

        int m = read();

        build(1,m,1);

        int q = read(),L,R;

        while(q--){

            L = read(),R = read();

            Line ans = query(L,R,1,m,1);

            if(ans.uv == -1) printf("%d\n",0);

            else printf("%d\n",dis[ans.u] + dis[ans.v] - dis[ans.uv] * 2);

        }

    }

    return 0;

}

巴特西

hdu 6010 路径交

hdu 6010 路径交(lca + 线段树)

题意：

思路:

最新文章

热门文章