公園散步的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。

在解题之前提交题解的代码会导致封禁。

Subtask 1~3

對每一筆詢問，枚舉每一點，BFS/DFS 算出它們的距離取 max，\(O(qn^2)\)。（TLE 60%）

Subtask 1~4

顯然一次 BFS/DFS 就可以得到一點和其餘所有點的距離，\(O(qn)\)。（TLE 80%）

Subtask 1~5

樹上的簡單路徑有兩種可能：單純由上到下（下到上）或由下到上再由上到下。前者很好處理（任意取根 DFS，對於在詢問中的點取 \(max(深度, max(子樹高度))\)），而後者可以在做前述 DFS 時紀錄每一點的子樹高度的最大跟次大，然後再 DFS 第二次，DFS 時要維護「往上再往下的爬最大簡單路徑長度」。確切地說，每次往下 DFS 時要用 \(max(目前值, max(這棵子樹外的最大子樹高度)) + 1\) 來更新這個值。這樣只需要兩次 DFS，\(O(n + q)\)。（AC 100%）

標程

C++（by tan7680）

#include<bits/stdc++.h>
#define maxn 100100
using namespace std;
int a[maxn],mx[maxn][2],ans[maxn];
bool vis[maxn];
vector<int>e[maxn];
void dfs(int x)
{
    if(vis[x])return;
    vis[x]=1;
    mx[x][0]=0;mx[x][1]=-1;
    for(int i=0;i<e[x].size();i++)
    {
        int k=e[x][i];
        if(vis[k])continue;
        dfs(k);
        if(mx[k][0]+1>mx[x][0])
        {
            mx[x][1]=mx[x][0];
            mx[x][0]=mx[k][0]+1;
        }
        else if(mx[k][0]+1>mx[x][1])
        {
            mx[x][1]=mx[k][0]+1;
        }
    }
}
void re_dfs(int x,int d)
{
    if(vis[x])return;
    vis[x]=1;
    ans[x]=max(mx[x][0],d);
    for(int i=0;i<e[x].size();i++)
    {
        int k=e[x][i];
        if(vis[k])continue;
        if(mx[k][0]==mx[x][0]-1)
            re_dfs(k,max(d,mx[x][1])+1);
        else re_dfs(k,max(d,mx[x][0])+1);
    }
}
int main()
{
    cin.tie(0);ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1);
    for(int i=1;i<=n;i++)assert(vis[i]);
    memset(vis,0,sizeof(vis));
    re_dfs(1,0);
    int Q;
    cin>>Q;
    while(Q--)
    {
        int n;
        cin>>n;
        cout<<ans[n]<<'\n';
    }
return 0;
}

Scala（by WillyPillow）

object x004 extends App {
  val n = io.StdIn.readInt()
  val _g = (1 until n).map(_ => io.StdIn.readLine().split(" ").map(_.toInt))
  val g = _g ++ _g.map(_.reverse) groupBy (_(0))

  val ans = Array.fill(n + 1)(0)
  val mxs = Array.fill(n + 1)((0, 0))

  def dfs(x: Int, p: Int, up: Int = 0): Int = {
    val vs = g.getOrElse(x, Seq.empty)
      .filter(_(1) != p)
      .map(y => dfs(y(1), x) + 1)
      .padTo(2, 0)
      .sorted
    mxs(x) = (vs.last, vs(vs.size - 2))
    vs.last
  }

  def dfs2(x: Int, p: Int, up: Int) {
    ans(x) = up max mxs(x)._1
    for (gx <- g.get(x); y <- gx if y(1) != p) {
      val u = if (mxs(y(1))._1 + 1 == mxs(x)._1) mxs(x)._2 else mxs(x)._1
      dfs2(y(1), x, (up max u) + 1)
    }
  }

  dfs(1, 1)
  dfs2(1, 1, 0)

  (1 to io.StdIn.readInt()).foreach(_ => println(ans(io.StdIn.readInt())))
}

目前没有评论。