2021牛客暑期多校训练营5 E Eert Esiwtib

2021牛客暑期多校训练营5 E Eert Esiwtib

八月 05, 2021

题目概述

给出一棵树，每条边上有一个位运算符，每个点有一个点权。现在有若干询问，每次询问会修改所有点的点权，并询问以$u$为根的子树中，从所有节点$v$到$u$的路径的位运算结果的位或和，位与和和异或和。

分析与解

这题首先启示我们，不要看到是树上路径就害怕。像这种从叶子走到根的路径，其实只要搞明白树形DP中怎么从儿子到父节点的边的转移，其实实现并不复杂。

这个题也是一样，我们记$dp[u][0/1/2]$表示以$u$​为根的子树的所有到根的路径的位或和，位与和和异或和。接下来就是转移。而这个转移其实就是一个分类讨论的范式题（考查上学期离散数学/数理逻辑学得怎么样 汗）

其实推导基本上就是用当前讨论的某种和对应的运算，来化简系列式子（相当于枚举$v$的子树中的所有点，增加了一段$v\to u$​的运算路径）比如边权为$XOR$,要计算的权和为$OR$：

然后方便起见只用考虑两三个变量的情况。所以上式通过列真值表可知化简为形如

具体细节见代码即可。

此外，注意初始化。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define min(a,b) (a)<(b) ? (a) : (b)
#define max(a,b) (a)>(b) ? (a) : (b)
LL mread() {
	LL ret=0,f=1;
	char c=getchar();
	while(c<'0' || c>'9') {
		if(c=='-')f=-1;
		c=getchar();
	}
	do {
		ret=ret*10+c-'0';
		c=getchar();
	} while('0'<=c && c<='9');
	return ret*f;
}
#define MAXN 200100
struct node {
	int v,len;
	node *nnext;
} pool[MAXN<<1],*h[MAXN<<1];
int cnt=-1;
void addedge(int u,int v,int len) {
	node *p=&pool[++cnt];
	p->v=v,p->len=len,p->nnext=h[u],h[u]=p;
	node *q=&pool[++cnt];
	q->v=u,q->len=len,q->nnext=h[v],h[v]=q;
}
int siz[MAXN];
LL a[MAXN],val[MAXN];
LL dp[MAXN][3],ans[MAXN][3];
int n,q;
struct qry {
	int d,u,id;
	LL val1,val2,val3;
} qwq[MAXN];
bool cmp1(qry s,qry t) {
	return s.d < t.d;
}
bool cmp2(qry s,qry t) {
	return s.id < t.id;
}
void dfs(int u,int fa) {
	int v;
	siz[u]=1;
	dp[u][0]=dp[u][2]=0,dp[u][1]=-1;//init!
	for(node *p=h[u]; p; p=p->nnext) {
		v=p->v;
		if(v!=fa) {
			dfs(v,u);
			siz[u]+=siz[v];
			if(p->len==0) {
				dp[u][0]|=(val[u]|dp[v][0]);
				dp[u][1]&=(val[u]|dp[v][1]);
				dp[u][2]^=(~val[u])&dp[v][2];
				dp[u][2]^=(siz[v] & 1) ? val[u] : 0;

			} else if(p->len==1) {
				dp[u][0]|=(val[u] & dp[v][0]);
				dp[u][1]&=(val[u] & dp[v][1]);
				dp[u][2]^=(val[u] & dp[v][2]);

			} else if(p->len==2) {
				dp[u][0]|=(~val[u]&dp[v][0])|(val[u]&~dp[v][1]);
				dp[u][1]&=(~val[u]&dp[v][1])|(val[u]&~dp[v][0]);
				dp[u][2]^=dp[v][2]^(siz[v]&1?val[u]:0);
			}
		}
	}
	ans[u][0]=dp[u][0],ans[u][1]=dp[u][1],ans[u][2]=dp[u][2];
	dp[u][0]|=val[u],dp[u][1]&=val[u],dp[u][2]^=val[u];
}
int main() {
	int f,s;
	n=mread(),q=mread();
	for(int i=1; i<=n; i++)a[i]=mread();
	for(int i=1; i<n; i++) {
		f=mread(),s=mread();
		addedge(i+1,f,s);
	}
	for(int i=1; i<=q; i++)qwq[i].d=mread(),qwq[i].u=mread(),qwq[i].id=i;
	sort(qwq+1,qwq+q+1,cmp1);
	qwq[0].d=-1;
	for(int i=1; i<=q; i++) {
//		printf("%d %d\n",qwq[i].u,qwq[i].d);
		if(qwq[i].d!=qwq[i-1].d) {
			for(int j=1; j<=n; j++)val[j]=a[j]+1ll*j*qwq[i].d;
			dfs(1,0);
		}
		qwq[i].val1=ans[qwq[i].u][0];
		qwq[i].val2=ans[qwq[i].u][1];
		qwq[i].val3=ans[qwq[i].u][2];
	}
	sort(qwq+1,qwq+q+1,cmp2);
	for(int i=1; i<=q; i++)printf("%lld %lld %lld\n",qwq[i].val1,qwq[i].val2,qwq[i].val3);
	return 0;
}