Submission #71105109

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
int N, M;
int x[114514], y[114514];
int add(int a, int b) {
  return a + b - M * (a + b >= M);
}
int mul(int a, int b) {
  return (int)((long long)a * b % M);
}
int ec[114514], *es[114514];
void ae(int f, int t) {
  es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
  if (es[f] == NULL) exit(2);
  es[f][ec[f]++] = t;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

int N, M;
int x[114514], y[114514];

int add(int a, int b) {
	return a + b - M * (a + b >= M);
}

int mul(int a, int b) {
	return (int)((long long)a * b % M);
}

int ec[114514], *es[114514];

void ae(int f, int t) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = t;
}

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (a > b) - (a < b);
}

/* 点set、範囲mulのセグメント木 */

#define KI_MAX (1 << 17) /* 131072 */

struct ki_s {
	int value;
	struct ki_s *next[2];
};

int ki_set_i(struct ki_s** pki, int ss, int se, int query, int value) {
	if (query < ss || se <= query) { /* 完全に外れている */
		return *pki == NULL ? 1 : (*pki)->value;
	}
	if (*pki == NULL) {
		*pki = malloc(sizeof(**pki));
		if (*pki == NULL) exit(2);
		**pki = (struct ki_s){ 1, { NULL, NULL } };
	}
	if (ss == query && se == query + 1) { /* セグメントがクエリに完全に含まれる */
		(*pki)->value = value;
	} else {
		int sm = ss + (se - ss) / 2;
		(*pki)->value = mul(
			ki_set_i(&(*pki)->next[0], ss, sm, query, value),
			ki_set_i(&(*pki)->next[1], sm, se, query, value)
		);
	}
	return (*pki)->value;
}

void ki_set(struct ki_s** pki, int query, int value) {
	ki_set_i(pki, 0, KI_MAX, query, value);
}

int ki_get_i(const struct ki_s* ki, int ss, int se, int qs, int qe) {
	if (ki == NULL) return 1; /* ここは全て初期値 */
	if (qe <= ss || se <= qs) { /* 完全に外れている */
		return 1;
	} else if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		return ki->value;
	} else {
		int sm = ss + (se - ss) / 2;
		return mul(
			ki_get_i(ki->next[0], ss, sm, qs, qe),
			ki_get_i(ki->next[1], sm, se, qs, qe)
		);
	}
}

int ki_get(const struct ki_s* ki, int qs, int qe) {
	return ki_get_i(ki, 0, KI_MAX, qs, qe);
}

/* 0：未探索、1～ec[node]：その番目(1-origin)の子だけ未探索、-1：探索済 */
int status[114514];
struct ki_s* children_info[114514];

int* memo[114514];

int get_idx(const int* array, int array_size, int target) {
	int l = 0, r = array_size - 1;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (array[m] == target) return m;
		else if (array[m] < target) l = m + 1;
		else r = m - 1;
	}
	return array_size;
}

int calc(int node, int parent) {
	int parent_id = get_idx(es[node], ec[node], parent);
	int ans;
	if (memo[node][parent_id]) return ~memo[node][parent_id];
	if (status[node] == 0) {
		int i;
		for (i = 0; i < ec[node]; i++) {
			if (es[node][i] != parent) ki_set(&children_info[node], i, add(calc(es[node][i], node), 1));
		}
		status[node] = parent_id >= ec[node] ? -1 : parent_id + 1;
	} else if (status[node] > 0) {
		/* 抜けたのと同じ頂点が親のときは、memo が使えるので、ここには来ないはず */
		ki_set(&children_info[node], status[node] - 1, add(calc(es[node][status[node] - 1], node), 1));
		status[node] = -1;
	}
	if (parent_id >= ec[node]) {
		ans = ki_get(children_info[node], 0, ec[node]);
	} else {
		ans = mul(
			ki_get(children_info[node], 0, parent_id),
			ki_get(children_info[node], parent_id + 1, ec[node])
		);
	}
	return ~(memo[node][parent_id] = ~ans);
}

int main(void) {
	int i;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 1; i < N; i++) {
		if (scanf("%d%d", &x[i], &y[i]) != 2) return 1;
		ae(x[i], y[i]);
		ae(y[i], x[i]);
	}
	for (i = 1; i <= N; i++) {
		if (ec[i] > 0) qsort(es[i], ec[i], sizeof(*es[i]), cmp);
		memo[i] = calloc(ec[i] + 1, sizeof(*memo[i]));
		if (memo[i] == NULL) return 2;
	}
	for (i = 1; i <= N; i++) printf("%d\n", calc(i, 0));
	return 0;
}

/*

木 → 迂回路とかは無い
黒い頂点のみを辿って到達できる → 黒い頂点は連結

頂点 v が黒である → そこを根として、どこまで黒を伸ばすか？

ある頂点が黒のとき、それぞれの子について
* 黒にしない → 1通り
* 黒にする → 再帰
これらの和を、全ての子について掛ける

*/

Submission Info

Judge Result