P6584 punch out

Write in front

Let's write an explanation for the title of zrm boss.

The code implementation of this problem is not difficult, but it exercises thinking, and there should be many solutions. It is really a subject of high quality.

Algorithm idea

First of all, obviously, when xiaoz walks to a subtree of the current node, the distance between youyou and xiaoz in this subtree will be reduced by \ (2 \) or \ (1 \) (minus \ (1 \) if and only if the distance between xiaoz's range and youyou is \ (1 \)). The relative distance between youyou and small Z on other nodes will not change.

Secondly, all the time Xiao Z spends on a sub tree is only related to the deepest node with youyou on the sub tree.

Therefore, little Z just needs to meet youyou who is the deepest from the starting point, and then meet youyou who is the deepest from the current node after eliminating this youyou. The rest of youyou will be completely eliminated in this process.

Using a method similar to finding the diameter of a tree, find the depth of the deepest youyou and the distance between the two farthest youyou through dfs. After the first youyou is eliminated, the deepest youyou depth is the depth of the first youyou in the farthest distance \ (\).

Time complexity \ (\ Theta(n) \).

Tips

  • After calculating the distance to be moved twice, directly subtracting the range \ (k \) from the distance can make the thinking easier. (the distance below refers to the distance after subtracting the range)

  • Deal with the parity of the two moving distances. If it is an odd number, just wait in place for a round after the distance is \ (1 \), so that the answer will not deteriorate. And reduce the distance of the second farthest youyou by \ (1 \).

  • Pay attention to the situation that you can destroy all of you in one round and the situation that you are within range in the second distance.

  • Note that the first round is shooting and moving, so the round of eliminating the last youyou is an additional round.

Code

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

const int Maxn = 4e5 + 5;

int n, m, x, y, k, T, ans;

struct e {
	int to, next;
} b[Maxn << 1];
int head[Maxn], cnt;

bool vis[Maxn];
bool yy[Maxn];

int dep1st, id1st, dep2nd, id2nd;
int Maxdep, Maxid;

void add(int u, int v)
{
	cnt++;
	b[cnt].next = head[u];
	b[cnt].to = v;
	head[u] = cnt;
}

inline int read()
{
	int f = 1, w = 0; char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
	for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
	return f * w;
}

void dfs(int t, int dep)
{
	if(vis[t]) return;
	vis[t] = 1;
	if((dep > Maxdep) && yy[t])
	{
		Maxdep = dep;
		Maxid = t;
	}
	for(int i = head[t]; i; i = b[i].next)
	{
		int tto = b[i].to;
		if(vis[tto]) continue;
		dfs(tto, dep + 1);
	}
}

int main()
{
	n = read() - 1;
	while(n--)
	{
		x = read(); y = read();
		add(x, y); add(y, x);
	}
	m = read();
	while(m--)
	{
		x = read();
		yy[x] = 1;
	}
	k = read(); T = read();
	dfs(T, 0);
	dep1st = Maxdep; id1st = Maxid;
	memset(vis, 0, sizeof(vis));
	Maxdep = 0; Maxid = 0;
	dfs(id1st, 0);
	dep2nd = Maxdep - dep1st; id2nd = Maxid;
	dep1st -= k; dep2nd -= k;
	if((dep1st) <= 0 && (dep2nd <= 0))
	{
		printf("%d", 1);
	}
	else if((dep2nd <= 0))
	{
		printf("%d", (dep1st/2) + (int)(dep1st & 1) + 1);
	}
	else
	{
		if(dep1st & 1)
		{
			dep2nd--;
			ans++; 
		}
		printf("%d", ans + (dep1st/2) + (dep2nd/2) + (int)(dep2nd & 1) + 1);
	}
	return 0;
}

Tags: Simulation

Posted by hcdarkmage on Wed, 11 May 2022 13:15:35 +0300