BZOJ3251 树上三角形

			    <div class="post_brief"><p>
原来在win下也有敲回车的bug。开心。</p>

这题坑啊。暴力还是很好想的，如果个数超过几十个的话就肯定有解了。比较坑的是两边之和大于第三边，边权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", &amp;n, &amp;m);
for (int i = 1; i &lt;= n; ++ i)
	scanf("%d", v + i);
for (int i = 1; i &lt; n; ++ i) {
	int u, v;
	scanf("%d%d", &amp;u, &amp;v);
	ep-&gt; t = v;
	ep-&gt; next = head[u];
	head[u] = ep ++;
	ep-&gt; t = u;
	ep-&gt; next = head[v];
	head[v] = ep ++;
}
bfs();
while (m --) {
	int t, x, y;
	scanf("%d%d%d", &amp;t, &amp;x, &amp;y);
	if (t == 0)
		puts(qry(x, y) ? "Y" : "N");
	else 
		v[x] = y;
}

}

Comments