BZOJ 4281: [ONTAK2015]Związek Harcerstwa Bajtockiego – [倍增/LCA]


题目传送门(BZOJ)

题解 :

每次询问先通过倍增求出LCA t,

然后判断dep[u]+dep[v]-2\times dep[t],及uv的长度是否大于给定的步数.

若大于等于, 则直接跳到v即可, 否则, 判断一下断点是在ut的链上还是tv的链上

直接通过倍增跳相应的步数即可.

代码 :

#include 
#include 
#include 
#include 
using namespace std;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
char buf[100000], *p1, *p2; const int N = 1000011;
inline int rd() {
    int x = 0; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc();
    return x;
}
#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)
struct Edge {
    int to;
    Edge *next;
}*h[N], e[N<<1];
int dep[N], f[20][N];
inline void addEdge(int u, int v) {
    static int _;
    Edge *tmp = &e[++_]; tmp->to = v; tmp->next = h[u]; h[u] = tmp;
}
void dfs(int p) {
    dep[p] = dep[f[0][p]]+1;
    for(int i = 1; i <= 19; i ++ ) f[i][p] = f[i-1][f[i-1][p]];
    rev(i, p) if(i->to != f[0][p]) {
        f[0][i->to] = p;
        dfs(i->to);
    }
}
int lca(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 19; ~i; i -- ) if(dep[f[i][x]] >= dep[y]) x = f[i][x];
    if(x == y) return x;
    for(int i = 19; ~i; i -- ) if(f[i][x] != f[i][y]) x = f[i][x], y = f[i][y];
    return f[0][x];
}
int jump(int x, int y) {
    for(int i = 19; ~i; i -- ) if((1<= v) p = jump(p, v);
        else p = jump(u, dep[p]+dep[u]-2*dep[t]-v);
        printf("%d ", p);
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注