#7 320ms 求卡常(复杂度应该是对的)
查看原帖
#7 320ms 求卡常(复杂度应该是对的)
738474
Erine楼主2022/12/3 19:42
#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

struct ios {
    inline char read() {
        static const int inlen = 1 << 18 | 1;
        static char buf[inlen], *s, *t;
        return (s == t) && (t = (s = buf) + fread(buf, 1, inlen, stdin)), s == t ? -1 : *s++;
    }
    template<typename T> inline ios& operator>> (T &x) {
        static char c11, boo;
        for (c11 = read(), boo = 0; !isdigit(c11); c11 = read()) {
            if (c11 == -1) return *this;
            boo |= c11 == '-';
        }
        for (x = 0; isdigit(c11); c11 = read()) x = x * 10 + (c11 ^ '0');
        boo && (x = -x);
        return *this;
    }
} fin;

struct exios {
    template<typename _CharT, typename _Traits = char_traits<_CharT>>
    struct typ {
        typedef basic_ostream<_CharT, _Traits>& (* end) (basic_ostream<_CharT, _Traits>&);
    };

    friend exios &operator<<(exios &out, int num) {
        if (num < 0) putchar('-'), num = -num;
        if (num >= 10) out << num / 10;
        putchar(num % 10 + '0');
        return out;
    }

    friend exios &operator<<(exios &out, const char * s) { printf("%s", s); return out; }
    friend exios &operator<<(exios &out, string s) { cout << s; return out; }
    friend exios &operator<<(exios &out, typ<char>::end e) { puts(""); return out; }
} fout;

const int maxn = 1e4 + 1;
const int maxm = 1e4 + 1;
const int maxq = 1e3 + 1;
const int maxv = 1e7 + 1;

struct edge {
	int to, next, w;
};

int n, m, k[maxq];
int head[maxn];
edge e[maxm << 1];
int cnt;

void add_edge(int u, int v, int w) {
	e[++cnt].to = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}

int tot, root, ans[maxq];
int mx[maxn];
int siz[maxn];
int vis[maxn];

void get_root(int u, int fa) {
	mx[u] = 0;
	siz[u] = 1;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].to;
		if (v == fa || vis[v]) continue;
		get_root(v, u);
		siz[u] += siz[v];
		mx[u] = max(mx[u], siz[v]);
	}
	mx[u] = max(mx[u], tot - siz[u]);
	if (mx[u] < mx[root]) {
		root = u;
	}
}

int dep[maxn], num;

void get_dep(int u, int d, int fa) {
	dep[++num] = d;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].to, w = e[i].w;
		if (v == fa || vis[v]) continue;
		get_dep(v, d + w, u);
	}
}

int book[maxv];

int get_sum(int u, int dis, int id) {
	num = 0;
	get_dep(u, dis, 0);
	int sum = 0;
	for (int i = 1; i <= num; ++i) {
		if (k[id] >= dep[i]) sum += book[k[id] - dep[i]];
		if (dep[i] < maxv) ++book[dep[i]];
	}
	for (int i = 1; i <= num; ++i) {
		if (dep[i] < maxv) book[dep[i]] = 0;
	}
	return sum;
}

void solve(int u) {
	for (int i = 1; i <= m; i++) {
		ans[i] += get_sum(u, 0, i);
	}
	vis[u] = true;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].to, w = e[i].w;
		if (vis[v]) continue;
		for (int j = 1; j <= m; j++) {
			ans[j] -= get_sum(v, w, j);
		}
		tot = siz[v];
		root = 0;
		get_root(v, u);
		solve(root);
	}
}

signed main() {
//	freopen("P3806_1.in", "r", stdin);
//	freopen("P3806_1.out", "w", stdout);
	fin >> n >> m;
	for (int i = 1; i <= n - 1; i++) {
		int u, v, w;
		fin >> u >> v >> w;
		add_edge(u, v, w);
		add_edge(v, u, w);
	}
	mx[0] = 1e9;
	for (int i = 1; i <= m; i++) {
		fin >> k[i];
	}
	tot = n;
	get_root(1, 0);
	solve(root);
	for (int i = 1; i <= m; i++) {
		cout << (ans[i] ? "AYE" : "NAY") << endl;
	}
	return 0;
}
2022/12/3 19:42
加载中...