Submission #763962

#	Time	Username	Problem	Language	Result	Execution time	Memory
763962		myrcella	Torrent (COI16_torrent)	C++17	0 / 100	71 ms	18416 KiB

torrent

// by szh
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

#define F first
#define S second
#define pii pair<LL, LL>
#define pb push_back
#define debug(x) cerr << #x << "=" << x << endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a; i < (b); i++)
#define MP make_pair
#define SZ(x) (static_cast<int>(x.size()))
#define MOD 1000000007
#define ALL(x) x.begin(), x.end()
void inc(int &a, int b) {a = (a+b)%MOD;}
void dec(int &a, int b) {a = (a-b+MOD)%MOD;}
int prod(int a,int b) {return LL(a)*LL(b)%MOD;}
int lowbit(int x) {return x&(-x);}

const int maxn = 3e5+10;

int n;
vector <int> edge[maxn];
int cnt = 0;
int x, y;
int dp[maxn];
int ans = 0;

int solve(int u, int fa) {
  vector <int> val;
  for (auto v : edge[u]) {
	if (v == fa) continue;
	solve(v, u);
	val.pb(dp[v]);
  }
  sort(ALL(val));
  reverse(ALL(val));
  rep(i, 0, SZ(val)) dp[u] = max(dp[u], val[i] + i + 1);
  return dp[u];
}

vector <int> node;

bool dfs(int u, int fa) {
  if (u == y) node.pb(u);
  if (u == y) return true;
  for (int v : edge[u]) {
	if (v == fa) continue;
	if (dfs(v, u)) {
	  node.pb(u);
	  return true;
    }
  }
  return false;
}

int main() {
  // freopen("input.txt","r",stdin);
  std::ios::sync_with_stdio(false); cin.tie(0);
  cin >> n >> x >> y;
  rep(i, 1, n) {
	int u, v;
	cin >> u >> v;
	edge[u].pb(v);
	edge[v].pb(u);
  }
  dfs(x, -1);
  if (SZ(node) == 2) {
	ans = max(solve(x, y), solve(y, x));
	cout << ans;
	return 0;
  }
  ans = max(solve(node[0], node[1]), solve(node.back(), node[SZ(node)-2]));
  //debug(ans);
  int lcur = 0, lcnt = SZ(edge[node[0]]) - 1;
  int rcur = SZ(node) - 1, rcnt = SZ(edge[node.back()]) - 1;
  while (1) {
	if (lcnt < rcnt) {
	  lcur++;
	  lcnt += SZ(edge[node[lcur]]) - 1;
	}
	else {
	  rcur--;
	  rcnt += SZ(edge[node[rcur]]) - 1;
    }
    if (lcur == rcur) break;
  }
  int tmp = 0;
  rep(i, 1, lcur) {
	tmp++;
	int u = node[i];
	vector <int> val;
	for (int v:edge[u]) {
	  if (v == node[i-1] or v == node[i+1]) continue;
	  dfs(v, u);
	  val.pb(dp[v]);
	}
	sort(ALL(val));
	reverse(ALL(val));
	for (auto it:val) tmp++, ans = max(ans, tmp + it);
  }
  //debug(ans);
  tmp = 0;
  for (int i = SZ(node) - 2; i > rcur; i--) {
	tmp++;
	int u = node[i];
	vector <int> val;
	for (int v:edge[u]) {
	  if (v == node[i-1] or v == node[i+1]) continue;
	  dfs(v, u);
	  val.pb(dp[v]);
	}
	sort(ALL(val));
	reverse(ALL(val));
	for (auto it:val) tmp++, ans = max(ans, tmp + it);
  }
  int u = node[lcur];
  vector <int> val;
  for (int v:edge[u]) {
	if (v == node[lcur-1] or v == node[rcur+1]) continue;
	dfs(v, u);
	val.pb(dp[v]);
  }
  //debug(ans);
  //debug(lcur);
  lcnt++, rcnt++;
  lcnt -= SZ(edge[node[lcur]]) - 1;
  rcnt -= SZ(edge[node[lcur]]) - 1;
  //debug(lcnt), debug(rcnt);
  for (auto it : val) {
	if (lcnt < rcnt) {
	  lcnt++;
	  ans = max(ans, lcnt + it);
    }
    else {
	  rcnt++;
	  ans = max(ans, rcnt + it);
    }
  }
  //debug(dp[3]);
  cout << ans << "\n";
  return 0;
}

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69