Good Bye 2023

發表於 更新於 分類於 ， Disqus： 文章字數： 967 所需閱讀時間 ≈ 3 分鐘
E(线段树)F(双连通分量)G()H1()H2()

https://codeforces.com/contest/1916

E. Happy Life in University(1s,512mb)

n(3e5)个点,根1的树, 每个点有颜色,求$\max(diff(u,lca(u,v)) * diff(v,lca(u,v)))$

其中$diff(u,v) =$,简单路径u到v上不同颜色的个数

我的思路

有想过dp,但是显然dp[u] =最长向下路径,是不行的因为 向上转移时需要知道是否有对应颜色

如果u,v是最大的方案

  • u,v没有祖先关系,那么u,v可以走到其下的任意位置,答案不会更差
  • u,v是祖先关系,那么一个向根走,一个向叶子走, 答案不会更差

因此 ans = max(f(叶子,叶子),f(根,叶子))

对于最近同色也是 可以简单的dfs+按照颜色的栈来做, 这样可以O(n)计算出每个点最近同色祖先

想过把树按照dfs序铺平成数组, 这样需要支持一种叫 整线段贡献

1
2
3
4
对于颜色c
  .....in[u]...in[v]...out[v]...out[u]
单点     +1       +1      -1       -1
线段     [   -1    ]     [    +1    ]

这样就变成 对于u,

找[in[u]....childa...] x [in[u]....childb...]

问题是这样支持线段后,如果直接用前缀和就有问题了

题解

啊, 就无脑线段树

seg = [叶子........] 到根的颜色不同数,但是在dfs过程中先认为上层节点颜色为未定义

那么

1
2
3
4
5
6
dfs1(u):
	for v in child[u]:
		dfs1(v)
	[左leaf[u]..右侧leaf[u]] += 1
	对于u的所有直接同色后继 -= 1 (首次dfs可以得到)
	找每个v的max, setMax(ans, 最大 * 次大)

代码

https://codeforces.com/contest/1916/submission/240672070

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for(ll i=(a);i<(ll)(n);i++)
// [,)
#define SEG_ROOT 0,0,nn
#define SEG_L (o*2+1)
#define SEG_R (o*2+2)
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid,r

ll read(){ll r;scanf("%lld",&r);return r;}
vector<int> e[300010];
int c[300010]; // 颜色
vector<int> cstk[300010]; // color stack
vector<int> childc[300010]; // 同色最近 child
array<int,2> lr[300010]; // [,)
pair<int,int> seg[4*300000+10]; // leaf {real value, -}, non-leaf {real max, lazy inc(未向下)}
void dfsc(int u,int &idx){
  if(cstk[c[u]].size()) childc[cstk[c[u]].back()].push_back(u);
  lr[u][0] = idx;
  if(e[u].size() == 0) { // leaf
    idx++;
  }else{
    cstk[c[u]].push_back(u);
    for(auto v:e[u]) dfsc(v, idx);
    cstk[c[u]].pop_back();
  }
  lr[u][1] = idx;
}
void up(int o,int inc){
  seg[o].first += inc;
  seg[o].second += inc;
}
void down(int o){
  if(seg[o].second){
    up(SEG_L, seg[o].second);
    up(SEG_R, seg[o].second);
    seg[o].second = 0;
  }
}
void add(int o,int l,int r,int ql,int qr,int inc){ // [,), [,)
  if(ql <= l and r <= qr) { up(o,inc); return ; }
  down(o);
  // [l,mid) [mid,r)
  if(ql < mid) add(SEG_L_CHILD, ql, qr, inc);
  if(qr > mid) add(SEG_R_CHILD, ql, qr, inc);
  seg[o].first = max(seg[SEG_L].first, seg[SEG_R].first);
}
void build(int o,int l,int r){ // [,) clean
  seg[o] = {0,0};
  if(l+1==r) return ;
  build(SEG_L_CHILD);
  build(SEG_R_CHILD);
}
int query(int o,int l,int r,int ql,int qr){
  if(ql<=l and r<=qr) return seg[o].first;
  down(o);
  int ret = 0;
  if(ql < mid) ret = max(ret, query(SEG_L_CHILD, ql, qr));
  if(qr > mid) ret = max(ret, query(SEG_R_CHILD, ql, qr));
  return ret;
}

void dfs1(int u,int nn, ll &ans){
  auto [l,r] = lr[u];
  for(auto v: e[u]) dfs1(v,nn,ans);
  for(auto v: childc[u]) add(SEG_ROOT,lr[v][0],lr[v][1],-1);
  add(SEG_ROOT, l, r, 1);
  vector<ll> mx;
  for(auto v: e[u]) mx.push_back(query(SEG_ROOT,lr[v][0], lr[v][1]));
  sort(begin(mx),end(mx));
  if(mx.size() > 0) ans = max(ans,mx[mx.size()-1]);
  if(mx.size() > 1) ans = max(ans,mx[mx.size()-1] * mx[mx.size()-2]);
}

void w(){
  int n = read();
  rep(i,1,n+1) e[i] = {};
  rep(i,1,n+1) childc[i] = {};
  rep(i,2,n+1) e[read()].push_back(i);
  rep(i,1,n+1) c[i] = read();
  int nn = 0;
  dfsc(1, nn);
  build(SEG_ROOT);
  ll ans = 1;
  dfs1(1, nn, ans);
  printf("%lld\n",ans);
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

总结

据说这场 后面有题可以OEIS 被大量downvote了,作者 74TrAkToR 也被大量downvote

E

评分只有2300

不知道为什么当时我都想到了所有必要的细节,以及线段树维护,却没有把这些细节组装起来,好蠢

参考

官方editorial: https://codeforces.com/blog/entry/124138

luogu: https://www.luogu.com.cn/problem/solution/CF1916E