BZOJ3251 树上三角形

原来在win下也有敲回车的bug。开心。

这题坑啊。暴力还是很好想的，如果个数超过几十个的话就肯定有解了。比较坑的是两边之和大于第三边，边权2³¹-1然后加起来就超过int的范围了。连WA若干次再见。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct edge {
	int t;
	edge *next;
};

const int maxn = 100009;
const int maxc = 88;

int n, m, v[maxn], d[maxn], fa[maxn], c[maxc];
edge *head[maxn], elst[maxn << 1], *ep(elst);

void bfs() {
	static int q[maxn];
	int hd(0), tl(1);
	q[0] = 1;
	memset(d, 0, sizeof(d));
	d[1] = 1;
	while (hd < tl) {
		int p(q[hd ++]);
		for (edge* e = head[p]; e; e = e-> next) 
			if (!d[e-> t]) {
				d[e-> t] = d[p] + 1;
				fa[e-> t] = p;
				q[tl ++] = e-> t;
			}
	}
}

bool qry(int x, int y) {
	int t(0);
	while (t < 60 && x != y) {
		if (d[x] > d[y]) {
			c[t ++] = v[x];
			x = fa[x];
		}
		else {
			c[t ++] = v[y];
			y = fa[y];
		}
	}
	if (x == y)
		c[t ++] = v[x];
	else
		return 1;
	sort(c, c + t);
	for (int i = 2; i < t; ++ i)
		if (c[i] - c[i - 1] < c[i - 2])
			return 1;
	return 0;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++ i)
		scanf("%d", v + i);
	for (int i = 1; i < n; ++ i) {
		int u, v;
		scanf("%d%d", &u, &v);
		ep-> t = v;
		ep-> next = head[u];
		head[u] = ep ++;
		ep-> t = u;
		ep-> next = head[v];
		head[v] = ep ++;
	}
	bfs();
	while (m --) {
		int t, x, y;
		scanf("%d%d%d", &t, &x, &y);
		if (t == 0)
			puts(qry(x, y) ? "Y" : "N");
		else 
			v[x] = y;
	}
}