题意
link.
题解
正解会 RE 几个点，是官方的栈空间太小了。
再者网上几篇题解都被我 hack 了，好不容易找到一组 hack 却不是我错了，而是 STD 错了……
所以我来写篇题解造福社会。
观察到 \(\max \{b_i \bmod b_j\}\)，则得到的结果一定比最大值小，则最大能取到次大。
那就维护一个子树内的最大、次大记为 \(bmax\)、\(b\_max\)。
但是我们需要在外面加一个 \(l\)。
似乎再维护一个子树外最大 \(l\) 就行了。
但是不对。
如果是只维护一个最大 \(lmax\)。
\[ \left\{ \begin{array} llmax + b\_max > bmax, ~bmax\\ lmax + b\_max < bmax, ~lmax + b\_max\\ lmax + b\_max = bmax, ? \end{array} \right. \]此时问号情况就无法维护。
所以还要维护一个次大 \(l\_max\)
（并且严格、不为零，否则就白维护了）；
但此时还是不对，因为第三种情况还需要考虑到次次大，因此还需要维护一个严格的次次大 \(b\_\_max\)。
\[ \left\{ \begin{array} llmax + b\_max > bmax, ~bmax\\ lmax + b\_max < bmax, ~lmax + b\_max\\ lmax + b\_max = bmax, ~\min(b\_max + l\_max, b\_\_max + lmax) \end{array} \right. \]但，还没完。
如果有 \(b\_max = bmax\) 的情况……虽然有，但显然不够优，就不用考虑啦。
完结撒花。
只不过维护 \(lmax\)、\(l\_max\) 的同时还要再维护一个 \(lmax\_\)、\(lmax\_\_\)，表示子树内的最大值然后转移得到 \(lmax\)。
非常恶心，真的要看吗。
namespace zqh {
const int N = 200005;
int n, q, fa[N];
vector<int> g[N];
struct node {
int bmax;
int b_max;
int b__max;
int lmax, l_max, l__max, lmax_;
int fht, tch;
node() {
bmax = b__max = b_max = -1;
fht = tch = lmax = l_max = l__max = lmax_ = 0;
}
} b[N];
void dfs(int u) {
if (!u) return;
if (g[u].empty()) {
b[u].bmax = b[u].fht;
b[u].lmax = b[u].tch;
return;
}
vector<int> q, p;
// cout << "hmz AK IOI\n";
q.push_back(b[u].fht);
for (int x : g[u]) {
dfs(x);
q.push_back(b[x].bmax);
q.push_back(b[x].b_max);
q.push_back(b[x].b__max);
p.push_back(b[x].lmax);
p.push_back(b[x].lmax_);
}
p.push_back(b[u].tch);
sort(p.begin(), p.end(), greater<int>());
sort(q.begin(), q.end(), greater<int>());
b[u].bmax = q[0];
b[u].b_max = q[1];
for (int i = 2; i < q.size(); i++)
if (q[i] != q[1]) {
b[u].b__max = q[i];
break;
}
b[u].lmax = p[0];
b[u].lmax_ = p[1];
for (int i = 1; i < p.size(); i++){
if (p[i] != b[u].lmax){
b[u].lmax_ = p[i];
break;
}
}
}
int get_l_max(int u) {
if (b[u].l_max) return b[u].l_max;
if (u == 1) {
return b[u].l_max = 0;
}
int t = fa[u];
int ans = b[t].tch;
for (int x : g[t]) {
if (x == u) continue;
ans = max(ans, b[x].lmax);
ans = max(ans, b[x].lmax_);
}
b[u].l_max = max(ans, get_l_max(t));
return b[u].l_max;
}
int get_l__max(int u) {
if (b[u].l__max) return b[u].l__max;
if (u == 1) {
return b[u].l__max = 0;
}
int t = fa[u];
vector<int> q;
q.push_back(b[t].tch);
for (int x : g[t]) {
if (x == u) continue;
q.push_back(b[x].lmax);
q.push_back(b[x].lmax_);
// ans = max(ans, b[x].lmax);
}
q.push_back(b[t].l_max);
q.push_back(get_l__max(t));
sort(q.begin(), q.end(), greater<int>());
for (int i = 0; i < q.size(); i++) {
if (q[i] != b[u].l_max) {
b[u].l__max = q[i];
break;
}
}
// b[u].l__max = q[1];
return b[u].l__max;
}
void calc_l_max() {
rep (i, 1, n) {
if (g[i].empty())
get_l_max(i);
}
}
void calc_l__max() {
rep (i, 1, n) {
if (g[i].empty())
get_l__max(i);
}
}
int dfs3(int u, int max_) {
int ans = 0;
if (b[u].fht != max_) {
ans = b[u].fht;
}
for (int x : g[u]) {
ans = max(ans, dfs3(x, max_));
}
return ans;
}
void init() {
cin >> n >> q;
rep (i, 2, n) {
cin >> fa[i];
g[fa[i]].push_back(i);
}
rep (i, 1, n) {
cin >> b[i].fht >> b[i].tch;
}
}
void solve() {
dfs(1);
calc_l_max();
calc_l__max();
rep (i, 1, n) {
if (b[i].l__max > b[i].l_max) swap(b[i].l__max, b[i].l_max);
if (b[i].lmax_ > b[i].lmax) swap(b[i].lmax_, b[i].lmax);
}
// rep (i, 460, 460) {
// cout << b[i].bmax << " " << b[i].b_max << " " << b[i].b__max << " " << b[i].l_max << " " << b[i].l__max << endl;
// }
//4053 3053 2016
//1000 990
// q = 0;
while (q--) {
int s;
cin >> s;
// cout << "[" << b[s].bmax << " " << b[s].b_max << " " << b[s].b__max << "]\n";
int l = b[s].l_max;
// cout << l << endl;
if (b[s].b_max == -1) {
cout << "0\n";
continue;
}
// if (l == 0 && b[s].bmax == b[s].b_max) {
// cout << dfs3(s, b[s].bmax) << endl;
// continue;
// }
if (l + b[s].b_max > b[s].bmax) {
cout << b[s].bmax << endl;
continue;
}
if (l + b[s].b_max < b[s].bmax) {
cout << l + b[s].b_max << endl;
continue;
}
// if (b[s].b__max == -1) {
// cout << max(b[s].b_max + b[s].l__max, 0LL) << endl;
// continue;
// }
// cout << b[s].l__max << endl;
if (b[s].b__max != b[s].b_max) {
int ans = 0;
if (b[s].l_max + b[s].b__max < b[s].bmax && b[s].b__max != -1)
ans = max(ans, b[s].l_max + b[s].b__max);
if (b[s].l__max + b[s].b_max < b[s].bmax && b[s].b_max != -1)
ans = max(ans, b[s].l__max + b[s].b_max);
cout << ans << endl;
}
// while(1);
// cout << min(b[s].bmax, b[s].b_max + b[s].l__max) << endl;
// }
}
}
void main() {
init();
solve();
}
} // namespace zqh
赛时 80，后面死活 95 分，心态崩了。
后面才终于调对了。
最后的最后，提供几组 hack，还要可以私信。
10 10
1 1 1 1 3 3 6 4 1 7 1
7 0
1 7
3 5
7 5
1 2
5 5
2 7
7 3
6 0
1
2
3
4
5
6
7
8
9
10
5
0
5
7
0
2
0
0
0
0
5
1 2 2 1
7 6
9 6
0 1
0 8
8 2
1
2
3
4
5
8
9
0
0
0