隐藏
「重庆联考2017D2T3」士兵训练 - 树形动规 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「重庆联考2017D2T3」士兵训练 - 树形动规

题目大意




题目分析

考虑不提升战斗力的情况:题目即询问结点子树内的两个权值模后的最大值。
显然该数不可能比子树中的严格次大更大(次大$\bmod$最大$=$次大)。
因此对于$S_i=1$直接输出次大值即可。

否则,设子树内的最大,严格次大,严格三大为$in.max,in.sec,in.thi$,子树外部的最大,严格次大为$out.max,out.sec$。
则答案有可能来自$min(in.sec+out.max,in.max)$,此时需满足条件$in.sec+out.max\neq in.max$。
反之若$in.sec+out.max=in.max$,则两个数模起来为$0$,显然我们应该将$in.sec+out.max$变得更小。

如果$in.sec+out.max=in.max$,即可用$max(in.thi+out.max,in.sec+out.sec)$更新答案。
注意特判一下最大值有多个的情况(此时可能选最大而不是严格次大)

因此我们只需要求出子树内/外部的最大,严格次大,严格三大和最大出现次数即可。

  • 做法一($O(n)$)
    子树内部可以用一次树形动规统计出答案。
    将树展开为Dfs序后,子树外部可以表示为Dfs序的前缀和后缀,用两个循环合并即可。
  • 做法二($O(n\log n)$)
    将树展开为Dfs序后,用线段树分别合并区间答案。

代码

做法二

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=200005;

int max(int a,int b) {
if(a>b)return a;
return b;
}

struct Tree {
int left,right,max,sec,thi,cnt;
Tree(int l=0,int r=0):left(l),right(r),max(-1),sec(-1),thi(-1),cnt(0) {}
};

void merge(Tree& a,int v,int cnt=0) {
if(v==a.max) {
a.cnt+=cnt;
return;
}
if(v==a.sec)return;
if(v>a.max) {
a.thi=a.sec;
a.sec=a.max;
a.max=v;
a.cnt=cnt;
} else if(v>a.sec) {
a.thi=a.sec;
a.sec=v;
} else if(v>a.thi)a.thi=v;
}
Tree merge(const Tree& a,const Tree& b) {
Tree ans=a;
merge(ans,b.max,b.cnt);
merge(ans,b.sec);
merge(ans,b.thi);
return ans;
}

struct Segment_Tree {
Tree tree[maxn*4];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right,const int* a) {
tree[index]=Tree(Left,Right);
if(Left==Right) {
tree[index].max=a[Left];
tree[index].cnt=1;
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid,a);
build(rs,mid+1,Right,a);
push_up(index);
}
void push_up(int index) {
int l=tree[index].left,r=tree[index].right;
tree[index]=merge(tree[ls],tree[rs]);
tree[index].left=l,tree[index].right=r;
}
Tree query(int index,int Left,int Right) {
if(Right<tree[index].left||Left>tree[index].right)return Tree();
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index];
Tree l=query(ls,Left,Right),r=query(rs,Left,Right);
return merge(l,r);
}
} st1,st2;

vector<int>edges[maxn];
int n,q,a[maxn],b[maxn],First[maxn],Last[maxn],cnt=0,M1[maxn],M2[maxn];

void AddEdge(int x,int y) {
edges[x].push_back(y);
}

void Dfs(int Now) {
First[Now]=++cnt;
M1[cnt]=a[Now];
M2[cnt]=b[Now];
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
Dfs(Next);
}
Last[Now]=cnt;
}

int main() {
n=Get_Int();
q=Get_Int();
for(int i=2; i<=n; i++) {
int x=Get_Int();
AddEdge(x,i);
}
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
b[i]=Get_Int();
}
Dfs(1);
st1.build(1,1,n,M1);
st2.build(1,1,n,M2);
for(int i=1; i<=q; i++) {
int x=Get_Int();
if(!edges[x].size()) {
puts("0");
continue;
}
Tree in=st1.query(1,First[x],Last[x]);
if(x==1) {
printf("%d\n",max(in.sec,0));
continue;
}
Tree out1=st2.query(1,1,First[x]-1),out2=st2.query(1,Last[x]+1,n);
Tree out=merge(out1,out2);
if(in.cnt==1) {
if(in.sec+max(out.max,0)!=in.max)printf("%d\n",min(in.sec+max(out.max,0),in.max));
else if(in.thi==-1)printf("%d\n",in.sec+max(out.sec,0));
else printf("%d\n",max(in.thi+max(out.max,0),in.sec+max(out.sec,0)));
} else {
if(max(out.max,0)==0)printf("%d\n",max(in.sec,0));
else printf("%d\n",in.max);
}
}
return 0;
}

姥爷们赏瓶冰阔落吧~