Description

给定一棵树上的三个点 \(a,b,c\)，你要制定两条起点和终点都在这三个点中的路径，使得两条路径重叠的节点最多。

Solution

感觉我的方法和大众不同，显然是珂以Hack的

考虑分类讨论，分三类：

\(a\) 点在这两条路径的起止点中出现 \(2\) 次。
\(b\) 点在这两条路径的起止点中出现 \(2\) 次。
\(c\) 点在这两条路径的起止点中出现 \(2\) 次。

下面只分析一类，即 \(a\) 出现两次（其实都一样的）。

如图，这时 \(\operatorname{LCA}(b,c)\) 不在 \(a\) 到 \(b\) 的简单路径上或\(\operatorname{LCA}(b,c)\) 不在 \(a\) 到 \(c\) 的简单路径上。

这就是说， \(\operatorname{LCA}(b,c)\) 不会被重复走过。

那么答案就是 \(\operatorname{dis}(a,\operatorname{LCA}(a,c))\) 和 \(\operatorname{dis}(a,\operatorname{LCA}(a,b))\) 中的最小值。（这个理解起来不难）

如图，这时 \(\operatorname{LCA}(b,c)\) 在 \(a\) 到 \(b\) 的简单路径上且\(\operatorname{LCA}(b,c)\) 在 \(a\) 到 \(c\) 的简单路径上。

这就是说， \(\operatorname{LCA}(b,c)\) 会被重复走过。

那么答案就是 \(\operatorname{dis}(a,\operatorname{LCA}(b,c))\) 。（这个理解起来更不难）

然后这题就愉快地做完了。

Code

#include<stdio.h>

#define reg register

#define ri reg int

#define rep(i, x, y) for(ri i = x; i <= y; ++i)

#define nrep(i, x, y) for(ri i = x; i >= y; --i)

#define DEBUG 1

#define INF 0x3fffffff

#define ll long long

#define il inline

#define swap(a, b) ((a) ^= (b) ^= (a) ^= (b))

#define max(i, j) (i) > (j) ? (i) : (j)

#define min(i, j) (i) < (j) ? (i) : (j)

#define read(i) io.READ(i)

#define print(i) io.WRITE(i)

#define push(i) io.PUSH(i)

struct IO {

#define MAXSIZE (1 << 20)

#define isdigit(x) (x >= '0' && x <= '9')

  char buf[MAXSIZE], *p1, *p2;

  char pbuf[MAXSIZE], *pp;

#if DEBUG

#else

  IO() : p1(buf), p2(buf), pp(pbuf) {}

  ~IO() {

    fwrite(pbuf, 1, pp - pbuf, stdout);

  }

#endif

  inline char gc() {

#if DEBUG

    return getchar();

#endif

    if(p1 == p2)

      p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);

    return p1 == p2 ? ' ' : *p1++;

  }

  inline bool blank(char ch) {

    return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';

  }

  template <class T>

  inline void READ(T &x) {

    register double tmp = 1;

    register bool sign = 0;

    x = 0;

    register char ch = gc();

    for(; !isdigit(ch); ch = gc())

      if(ch == '-') sign = 1;

    for(; isdigit(ch); ch = gc())

      x = x * 10 + (ch - '0');

    if(ch == '.')

      for(ch = gc(); isdigit(ch); ch = gc())

        tmp /= 10.0, x += tmp * (ch - '0');

    if(sign) x = -x;

  }

  inline void READ(char *s) {

    register char ch = gc();

    for(; blank(ch); ch = gc());

    for(; !blank(ch); ch = gc())

      *s++ = ch;

    *s = 0;

  }

  inline void READ(char &c) {

    for(c = gc(); blank(c); c = gc());

  }

  inline void PUSH(const char &c) {

#if DEBUG

    putchar(c);

#else

    if(pp - pbuf == MAXSIZE) {

      fwrite(pbuf, 1, MAXSIZE, stdout);

      pp = pbuf;

    }

    *pp++ = c;

#endif

  }

  template <class T>

  inline void WRITE(T x) {

    if(x < 0) {

      x = -x;

      PUSH('-');

    }

    static T sta[35];

    T top = 0;

    do {

      sta[top++] = x % 10;

      x /= 10;

    } while(x);

    while(top)

      PUSH(sta[--top] + '0');

  }

  template <class T>

  inline void WRITE(T x, char lastChar) {

    WRITE(x);

    PUSH(lastChar);

  }

} io;

struct Edge {

  int to, nxt, val;

} e[1000010];

int n, q, cnt, head[1000010], fath[1000010][22], dep[1000010], s, lg[500010];

void add(int u, int v, int val) {

  e[++cnt].to = v;

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

  e[cnt].val = val;

  head[u] = cnt;

}

void dfs(int now, int fa) {

  dep[now] = dep[fa] + 1;

  fath[now][0] = fa;

  rep(i, 1, lg[dep[now]]) fath[now][i] = fath[fath[now][i - 1]][i - 1];

  for(int i = head[now]; i; i = e[i].nxt) if(e[i].to != fa) dfs(e[i].to, now);

}

int lca(int x, int y) {

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

  while(dep[x] > dep[y]) x = fath[x][lg[dep[x] - dep[y]] - 1];

  if(x == y) return x;

  nrep(i, lg[dep[x]] - 1, 0) if(fath[x][i] != fath[y][i]) x = fath[x][i], y = fath[y][i];

  return fath[x][0];

}

int abs(int x) { return x < 0 ? -x : x; }

int dis(int x, int y) {

	int l = lca(x, y);

	return abs(dep[l] - dep[x]) + abs(dep[l] - dep[y]);

}

int check(int a, int b, int c) {

	if(dis(a, c) + dis(b, c) == dis(a, b)) return 1;

	return 0;

}

int solve(int a, int b, int c) {

  if(check(a, b, lca(b, c)) && check(a, c, lca(b, c))) return dis(a, lca(b, c));

  return min(dis(a, lca(a, b)), dis(a, lca(a, c)));

}

int main() {

  read(n), read(q);

  rep(i, 2, n) {

    int x;

    read(x);

    add(x, i, 1), add(i, x, 1);

  }

  rep(i, 1, n) lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);

  dfs(1, 0);

  rep(i, 1, q) {

    int x, y, z;

    read(x), read(y), read(z);

    int ans = max(solve(x, y, z), max(solve(y, x, z), solve(z, x, y)));

    printf("%d\n", ans);

  }

  return 0;

}

巴特西

CF832D题解

Description

Solution

Code

最新文章

热门文章