# 756 div3 E1 E2（dfs F（双指针

# 756 div3 E1 E2（dfs F（双指针

E1. Escape The Maze (easy version)
题意：
一个人从节点 1 1 1 开始出发，但是有 k k k 个阻碍，起点在 x i x_i xi​ 节点，如果中途遇到阻碍则会输掉游戏，每秒只能移动到相邻的节点，也可以不移动。
判断他能不能一定走到一个叶子节点，而不碰到阻碍。
思路：
显然他能胜利的条件就是存在一个叶子节点， 1 1 1 到叶子节点的距离小于 k k k 个阻碍到叶子节点的距离
a n s [ i ] ans[i] ans[i] 数组表示阻碍到节点 i i i 的最小距离
d f s dfs dfs 暴搜两次即可
先预处理 a n s ans ans 数组，然后再判断一遍即可
code：

#include
#define endl 'n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define eps 1e-6
using namespace std;
const int maxn = 2e5 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m, k;
ll ans[maxn];
bool vis[maxn];
vector  v[maxn];

bool dfs(int x, int step){
	vis[x] = 1;
	bool f = 0;
	for(int i = 0; i < v[x].size(); ++i){
		if(!vis[v[x][i]]){
			ans[v[x][i]] = min(ans[x] + 1, ans[v[x][i]]);
			if(dfs(v[x][i], step + 1)) f = 1;
			ans[x] = min(ans[x], ans[v[x][i]] + 1);
		}
	}
//	cout << x << " " << ans[x] << " " << step << endl;
	if(x != 1 && v[x].size() == 1 && step < ans[x] || f) return 1;
	else return 0;
}
void work()
{
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) vis[i] = 0, ans[i] = inf, v[i].clear();	
	for(int i = 1, x; i <= k; ++i){
		cin >> x;
		ans[x] = 0;
	}
	for(int i = 1, x, y; i < n; ++i){
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1, 0);// 先预处理 ans 数组
	for(int i = 1; i <= n; ++i) vis[i] = 0;
	if(dfs(1, 0)) cout << "YESn";
	else cout << "NOn";
}

int main()
{
	ios::sync_with_stdio(0);
	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}

E2. Escape The Maze (hard version)
题意：
在 E 1 E1 E1 的基础上，如果游戏必输，那么最少保留多少个阻碍。
思路：
记忆化搜索
s t e p > = a n s [ x ] step>=ans[x] step>=ans[x] 这个判断
因为这是棵树，所以要经过 x x x 的子节点必然要经过 x x x，如果 s t e p > = a n s [ x ] step>=ans[x] step>=ans[x]，那么访问到 x x x 的子节点也一定满足这个不等式，所以只需要在 x x x 节点放一个阻碍即可
code：

#include
#define endl 'n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define eps 1e-6
using namespace std;
const int maxn = 2e5 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m, k;
ll ans[maxn];
bool vis[maxn];
vector  v[maxn];

int dfs(int x, int step){
	vis[x] = 1;
	bool f = 0;
	int sum = 0;
	for(int i = 0; i < v[x].size(); ++i){
		if(!vis[v[x][i]]){
			ans[v[x][i]] = min(ans[x] + 1, ans[v[x][i]]);
			int tmp = dfs(v[x][i], step + 1);
			if(tmp == -1) f = 1;
			else sum += tmp;
			ans[x] = min(ans[x], ans[v[x][i]] + 1);
		}
	}
	if(x != 1 && v[x].size() == 1 && step < ans[x] || f) return -1;
	else if(step >= ans[x]) return 1;
	else return sum;
}
void work()
{
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) vis[i] = 0, ans[i] = inf, v[i].clear();	
	for(int i = 1, x; i <= k; ++i){
		cin >> x;
		ans[x] = 0;
	}
	for(int i = 1, x, y; i < n; ++i){
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1, 0);
	for(int i = 1; i <= n; ++i) vis[i] = 0;
	cout << dfs(1, 0) << endl;
}

int main()
{
	ios::sync_with_stdio(0);
	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}

F. ATM and Students
题意：
给定一个长度为 n n n 的序列，初始和为 m m m，找一段最长的连续子序列，满足 m + ∑ i = l i = r a i > = 0 m + sum_{i=l}^{i=r}a_i>=0 m+∑i=li=r​ai​>=0
思路：
双指针板子
code：

#include
#define endl 'n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define eps 1e-6
using namespace std;
const int maxn = 2e5 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
ll a[maxn];

void work()
{
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	ll l = 1, r = 1, sum = m, ans = 0;
	ll x = -1, y = -1;
	while(l <= n)
	{
		while(r <= n && sum + a[r] >= 0) sum += a[r], ++r;
		if(ans < r - l){
			ans = r - l;
			x = l, y = r - 1;
		}
		sum -= a[l];
		++l;
	}
	if(y == -1) cout << -1 << endl;
	else cout << x << " " << y << endl;
}

int main()
{
	ios::sync_with_stdio(0);
	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}