結果

問題 No.1790 Subtree Deletion
コンテスト
ユーザー 👑 ygussany
提出日時 2021-12-19 00:37:04
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 170 ms / 3,000 ms
コード長 2,484 bytes
コンパイル時間 361 ms
コンパイル使用メモリ 32,000 KB
実行使用メモリ 22,400 KB
最終ジャッジ日時 2024-09-15 14:20:11
合計ジャッジ時間 3,156 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>

typedef struct {
	int left, right, lb;
	long long sum;
} lazy_seg_node;

int leaf[200001];

void init_node(lazy_seg_node v[], int k, int l, int r)
{
	v[k].left = l;
	v[k].right = r;
	v[k].sum = 0;
	v[k].lb = 1;
	if (l < r) {
		init_node(v, k << 1, l, (l + r) / 2);
		init_node(v, (k << 1) ^ 1, (l + r) / 2 + 1, r);
	} else leaf[l] = k;
}

void update_segment(lazy_seg_node v[], int k, int l, int r, int b)
{
	int i, j;
	if (v[k].left > r || v[k].right < l) return;
	else if (v[k].left >= l && v[k].right <= r) {
		v[k].lb *= b;
		v[k].sum *= b;
		for (j = k, i = j >> 1; i > 0; j = i, i >>= 1) v[i].sum = v[j].sum ^ v[j^1].sum;
	} else {
		if (v[k].lb != 1) {
			j = k << 1;
			v[j].sum *= v[k].lb;
			v[j^1].sum *= v[k].lb;
			v[j].lb *= v[k].lb;
			v[j^1].lb *= v[k].lb;
			v[k].lb = 1;
		}
		update_segment(v, k << 1, l, r, b);
		update_segment(v, (k << 1) ^ 1, l, r, b);
	}
}

long long get_sum(lazy_seg_node v[], int k, int l, int r)
{
	if (k == 1) update_segment(v, 1, l, r, 1);
	if (v[k].left > r || v[k].right < l) return 0;
	else if (v[k].left >= l && v[k].right <= r) return v[k].sum;
	else return get_sum(v, k << 1, l, r) ^ get_sum(v, (k << 1) ^ 1, l, r);
}

typedef struct Edge {
	struct Edge *next;
	int v;
	long long label;
} edge;

int DFS(edge* adj[], int u, int flag[], int first[], int last[], long long sum[])
{
	flag[u] = 1;
	first[u] = ++flag[0];
	edge *p;
	for (p = adj[u]; p != NULL; p = p->next) {
		if (flag[p->v] == 0) DFS(adj, p->v, flag, first, last, sum);
		else sum[u] ^= p->label;
	}
	last[u] = ++flag[0];
}

int main()
{
	int i, N, u, w;
	long long l;
	edge *adj[100001] = {}, e[200001], *p;
	scanf("%d", &N);
	for (i = 0; i < N - 1; i++) {
		scanf("%d %d %lld", &u, &w, &l);
		e[i*2].v = w;
		e[i*2+1].v = u;
		e[i*2].label = l;
		e[i*2+1].label = l;
		e[i*2].next = adj[u];
		e[i*2+1].next = adj[w];
		adj[u] = &(e[i*2]);
		adj[w] = &(e[i*2+1]);
	}
	
	int first[100001], last[100001], flag[100001] = {};
	long long sum[100001] = {};
	DFS(adj, 1, flag, first, last, sum);
	
	lazy_seg_node v[524288];
	init_node(v, 1, 1, N * 2);
	for (u = 1; u <= N; u++) v[leaf[first[u]]].sum = sum[u];
	for (i = leaf[N*2]; i >= 1; i--) if (v[i].left < v[i].right) v[i].sum = v[i<<1].sum ^ v[(i<<1)^1].sum;
	
	int Q, t, x;
	scanf("%d", &Q);
	for (i = 1; i <= Q; i++) {
		scanf("%d %d", &t, &x);
		if (t == 1) update_segment(v, 1, first[x], last[x], 0);
		else printf("%lld\n", get_sum(v, 1, first[x] + 1, last[x]));
	}
	fflush(stdout);
	return 0;
}
0