这是什么毒瘤题目啊!!路过dalao帮我看一下思路吧
查看原帖
这是什么毒瘤题目啊!!路过dalao帮我看一下思路吧
519384
Link_Cut_Y楼主2022/1/17 14:55
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define x first
#define y second
#include <queue>

using namespace std;

typedef pair<int, int> PII;
const int N = 100010, M = N << 1;
int h[N], e[M], ne[M], idx;
int top[N], dep[N], sz[N], cnt;
int nw[N], w[N], id[N];
int fa[N], son[N];
int n, q;

void add(int a, int b)
{
	e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

void dfs1(int u, int father, int depth)
{
	fa[u] = father, dep[u] = depth, sz[u] = 1;
	
	for (int i = h[u]; i; i = ne[i])
	{
		int j = e[i];
		if (j == father) continue;
		dfs1(j, u, depth + 1);
		sz[u] += sz[j];
		if (sz[son[u]] < sz[j]) son[u] = j;
	}
}

void dfs2(int u, int t)
{
	top[u] = t, id[u] = ++ cnt, nw[cnt] = w[u];
	if (!son[u]) return;
	dfs2(son[u], t);
	
	for (int i = h[u]; i; i = ne[i])
	{
		int j = e[i];
		if (j == fa[u] || j == son[u]) continue;
		dfs2(j, j);
	}
}

struct Tree
{
	int l, r;
	PII maxn;
}tr[N << 2];

PII get_max(PII a, PII b)
{
	if (a.x == b.x) return {a.x, max(a.y, b.y)};
	if (a.y >= b.x) return {a.x, a.y};
	if (b.y >= a.x) return {b.x, b.y};
	
	return {max(a.x, b.x), min(a.x, b.x)};
}

void pushup(int u)
{
	tr[u].maxn = get_max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}

void build(int u, int l, int r)
{
	tr[u] = {l, r, {0, 0}};
	if (l == r)
	{
		tr[u].maxn = {w[r], 0};
		return;
	}
	
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void modify(int u, int k, int v)
{
	if (tr[u].l == k && tr[u].r == k)
	{
		tr[u].maxn.x += v;
		nw[k] += v;
		return;
	}
	
	int mid = tr[u].l + tr[u].r >> 1;
	if (k <= mid) modify(u << 1, k, v);
	else modify(u << 1 | 1, k, v);
	pushup(u);
}

PII query(int u, int l, int r)
{
	if (tr[u].l >= l && tr[u].r <= r) return tr[u].maxn;
	
	PII res = {0, 0};
	int mid = tr[u].l + tr[u].r >> 1;
	
	if (l <= mid) res = query(u << 1, l, r);
	if (r > mid) res = get_max(res, query(u << 1 | 1, l, r));
	
	return res;
}

PII query_path(int u, int v)
{
	PII res = {0, 0};
	while (top[u] != top[v])
	{
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		res = get_max(res, query(1, id[top[u]], id[u]));
		u = fa[top[u]];
	}
	
	if (dep[u] < dep[v]) swap(u, v);
	res = get_max(res, query(1, id[v], id[u]));
	
	return res;
}

PII query_tree()
{
	priority_queue<int, vector<int>> heap;
	
	for (int i = 1; i <= n; i ++ ) heap.push(nw[i]);
	
	int a, b;
	a = heap.top(), heap.pop();
	
	while (heap.top() == a) heap.pop();
	b = heap.top();
	
	return {a, b};
}

int main()
{
	scanf("%d", &n);
	
	for (int i = 1; i <= n - 1; i ++ )
	{
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b), add(b, a);
	}
	
	for (int i = 1; i <= n; i ++ )
		scanf("%d", &w[i]);
	
	dfs1(1, -1, 1), dfs2(1, 1), build(1, 1, n);
	
	scanf("%d", &q);
	
	
	while (q -- )
	{
		int opt, u, v;
		scanf("%d%d%d", &opt, &u, &v);
		if (opt == 0)
		{
			modify(1, id[u], v);
		}
		if (opt == 1)
		{
			PII res = query_path(u, v);
			if (res.y == 0)
			{
				puts("-1");
				continue;
			}
			cout << res.y % res.x << ' ';
			res = query_tree();
			cout << res.y % res.x << endl;
		}
	}
	
	return 0;
}
2022/1/17 14:55
加载中...