cjwdyzxfblzs @ 2023-06-07 19:46:11
在学淀粉质的时候先做了Tree这道题目,我看这道模板提就是改一下参数,把
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010, M = N * 2;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
int p[N];
int q[N];
void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }
int get_size(int u, int fa)
{
if (st[u])
return 0;
int res = 1;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == fa)
continue;
res += get_size(j, u);
}
return res;
}
int get_wc(int u, int fa, int tot, int &wc)
{
if (st[u])
return 0;
int sum = 1, ms = 0;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == fa)
continue;
int t = get_wc(j, u, tot, wc);
ms = max(ms, t);
sum += t;
}
ms = max(ms, tot - sum);
if (ms <= tot / 2)
wc = u;
return sum;
}
void get_dist(int u, int fa, int dist, int &qt)
{
if (st[u])
return;
q[qt++] = dist;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == fa)
continue;
get_dist(j, u, dist + w[i], qt);
}
}
int get(int a[], int k)
{
sort(a, a + k);
int res = 0;
for (int i = k - 1, j = -1; i >= 0; i--)
{
while (j + 1 < i && a[j + 1] + a[i] == m) /* 这里把 小于等于 替换成了 等于 */
j++;
j = min(j, i - 1);
res += j + 1;
}
return res;
}
int calc(int u)
{
if (st[u])
return 0;
int res = 0;
get_wc(u, -1, get_size(u, -1), u);
st[u] = true;
int pt = 0;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i], qt = 0;
get_dist(j, -1, w[i], qt);
res -= get(q, qt);
for (int k = 0; k < qt; k++)
{
if (q[k] == m) /* 这里也是把 小于等于 替换成了 等于 */
res++;
p[pt++] = q[k];
}
}
res += get(p, pt);
for (int i = h[u]; i != -1; i = ne[i])
res += calc(e[i]);
return res;
}
int ak;
int main()
{
cin >> n;
cin >> ak;
memset(h, -1, sizeof h);
// memset(st, 0, sizeof st);
for (int i = 0; i < n - 1; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
while (ak--)
{
memset(st, false, sizeof(st));
cin >> m;
if (calc(2) || m == 0)
cout << "AYE" << endl;
else
cout << "NAY" << endl;
}
return 0;
}
by heaksicn @ 2023-06-07 19:50:51
@sjzez__chess 主函数里面是不是应该找重心在 calc
by cjwdyzxfblzs @ 2023-06-07 19:52:58
@heaksicn 我的重心在calc里面找的呀
by cjwdyzxfblzs @ 2023-06-07 19:53:41
@heaksicn 我这个是有什么问题吗???
by crimson000 @ 2023-06-07 19:54:13
小于等于满足单调性但是等于不满足单调性吧,所以不能用双指针应该
by cjwdyzxfblzs @ 2023-06-07 19:56:38
@crimson000 有道理欸