链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3251

题意就是给一棵树，点权，然后查询一条链上是否有3个点的点权能组成一个三角形。

注意到三角形任意2边之和大于第三边，然后最坏的情况类似于斐波那契数列，大约4 50左右的时候，就会超int。所以当链的长度大于45的时候，返回true，否则就暴力判断是否可行。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int maxn = 101110;

int N, Q;
vector<int> next[maxn];
long long val[maxn];
int par[maxn], dep[maxn];

void dfs(int u) {
	for (int i = 0; i < next[u].size(); i++) {
		int v = next[u][i];
		//if (dep[v]) continue;
		dep[v] = dep[u] + 1;
		dfs(v);
	}
}

bool check(int x, int y) {
	int cnt = 0;
	long long num[55];
	for ( ; dep[x] > dep[y]; x = par[x]) {
		num[cnt++] = val[x];
		if (cnt > 45) return true;
	}
	for ( ; x != y; x = par[x], y = par[y]) {
		num[cnt++] = val[x];
		num[cnt++] = val[y];
		if (cnt > 45) return true;
	}
	num[cnt++] = val[y];
	if (cnt < 3) 
		return false;
	sort(num, num + cnt);
	for (int i = 0; i + 2 < cnt; i++) {
		if (num[i] + num[i+1] > num[i+2])
			return true;
	}
	return false;
}

void init() {
	for (int i = 0; i < maxn; i++) {
		next[i].clear();
		dep[i] = 0;
		val[i] = 0;
		par[i] = 0;
	}
	par[1] = -1;
	scanf("%d %d", &N, &Q);
	for (int i = 1; i <= N; i++)
		scanf("%d", &val[i]);
	for (int i = 1; i < N; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		par[y] = x;
		next[x].push_back(y);
	}
	dep[1] = 1;
	dfs(1);
}

void work() {
	for (int i = 0; i < Q; i++) {
		int opt, x, y;
		scanf("%d %d %d", &opt, &x, &y);
		if (opt == 1)
			val[x] = y;
		else {
			if (dep[x] < dep[y])
				swap(x, y);
			if (x == y || x == par[y] || y == par[x]) {
				puts("N");
				continue;
			}
			if (check(x, y) == true)
				puts("Y");
			else puts("N");
		}
	}
}

int main() {
	init();
	work();
	return 0;
}