Codeforces Round #620 (Div. 2) | LIS , LCA

D.Shortest and Longest LIS

题意：
用1-n的数根据相邻项的大小关系构造两个序列，使得len(LIS)最小和最长
分析：
最小：每一段上升序列递减(eg: 678 345...)
最大：因为LIS最大的时候，元素是由每个下降段的中一个元素构成的。所以只要使得所有下降序列呈上升趋势即可。(eg: 321 654)
代码：

#include <bits/stdc++.h>
using namespace std;
 
const int MAX_N = 200000;
int ans[MAX_N + 5];
 
int main()
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n, i, j;
		string s;
		cin >> n >> s;
 
		int num = n, last = 0;
		for (i = 0; i < n; i++)
		{
			if (i == n - 1 || s[i] == '>')
			{
				for (j = i; j >= last; j--)
					ans[j] = num--;
				last = i + 1;
			}
		}
		for (i = 0; i < n; i++)
			cout << ans[i] << (i == n - 1 ? '\n' : ' ');
 
		num = 1, last = 0;
		for (i = 0; i < n; i++)
		{
			if (i == n - 1 || s[i] == '<')
			{
				for (j = i; j >= last; j--)
					ans[j] = num++;
				last = i + 1;
			}
		}
		for (i = 0; i < n; i++)
			cout << ans[i] << (i == n - 1 ? '\n' : ' ');
	}
}

E.1-Trees and Queries

题意：
给你一棵树，联通a, b 能不能使得x 到 y的距离为k
分析：
a到b有三种方式：
1、a不经过添加边到b
2、a->x, x - >y(添加边， 下同), y ->b
3、a->y, y -> x, x -> b
合法的路径应该是 <= k && 跟k的奇偶性相同。
添加边要走的话走一次即可，因为走多次并不会影响最终距离的奇偶性。
最后检查三种方式的合法性，2和3的奇偶性其实是一样的，所以直接取min即可。
距离通过LCA求
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(a, b) cout << a << b << endl
#define fi first
#define se second
const int maxn = 1e6;
const int inf = 0x3f3f3f3f;
struct edge
{
	int ep, nex;
	edge(int a = 0, int b = 0) : ep(a), nex(b){}
}e[maxn];
int head[maxn], tot;
int n;
void addedge(int sp, int ep)
{
	e[tot] = edge(ep, head[sp]);
	head[sp] = tot++;
	e[tot] = edge(sp, head[ep]);
	head[ep] = tot++;
}
void init()
{
	mem(head, -1), tot = 0;
}

int fa[maxn][20];
int depth[maxn];
void build(int now, int f, int dep)
{
	fa[now][0] = f, depth[now] = dep;
	for(int i = 1; i <= 19; i++)
		fa[now][i] = fa[fa[now][i - 1]][i - 1];
	for(int i = head[now]; ~i; i = e[i].nex)
	{
		int ep = e[i].ep;
		if(ep == f) continue;
		build(ep, now, dep + 1);
	}
}

int len(int x, int y)
{
	if(depth[y] < depth[x]) swap(x, y);
	int dif = depth[y] - depth[x];
	int dis = dif;
	for(int i = 19; i >= 0; i--)
		if(dif & (1 << i))
			y = fa[y][i];
	if(x == y) return dis;
	for(int i = 19; i >= 0; i--)
		if(fa[x][i] != fa[y][i])
			x = fa[x][i], y = fa[y][i], dis += 2 * (1 << i);
	return dis + 2;	
}

int main()
{
	close();
	cin >> n;
	init();
	for(int i = 1; i <= n - 1; i++)
	{
		int x, y;
		cin >> x >> y;
		addedge(x, y);
	}
	int m; cin >> m;
	build(1, -1, 1);
	while(m--)
	{
		int x, y, a, b, k;
		cin >> x >> y >> a >> b >> k;
		int without = len(a, b);
		int with = min(len(a, x) + len(y, b), len(a, y) + len(x, b)) + 1;
		if(without % 2 == k % 2 && without <= k || with % 2 == k % 2 && with <= k) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
}