solution

Posted on Edited on Views: Word count in article: 807 Reading time ≈ 3 mins.

a $i$ a

啊 $i$ 啊

等于 $i$ 的

先假设这个过程在树上进行。

考虑暴力，模拟这个过程，对一条边选择哪个点移动进行决策。发现一定是移动剩余距离最大的点，因为如果移动距离较小的点，调整一定不劣。

但是模拟这个过程无法优化，没有前途。调整思路，不关注时间，而关注每条边，答案显然等于所有边最后经过时间的最大值，如果能计算出每个点 $i$ 到 $x$ 的时间，那么 $(x,p_x)$ 最后经过时间可以通过上述贪心求出。因为每次移动剩余距离最大的点，我们只需要关心所有经过 $(x,p_x)$ 的路径的出发点 $a_i$。

考察特殊情况，如果只有 $1$ 条路径，那么显然到达 $x$ 的时间为 $d_{a_i}-d_{x}$，其中 $d_i$ 表示 $i$ 点的深度。

拓展到一般情况，发现会出现某个时刻，两个点在同一位置，造成堵塞的情况。这种情况不好考虑，不妨猜测不用考虑这种情况，直接另 $a_i$ 到 $x$ 的时间为 $d_{a_i}-d_{x}$ 而不影响答案。证明考虑如果 $u,v$ 两点 $t$ 时刻在 $z$ 点堵塞了，那么到达 $p_z$ 的时刻应为 $t+1,t+2$，但是观察到我们可以将堵塞时间延后，将 $(z,p_z)$ 边扩容，到达 $p_z$ 时刻变为 $t+1,t+1$，但是他们在 $p_z$ 仍会堵塞，那么得到一个结论：将 $(x,p_x)$ 子树内的边扩容为 $+\infty$，不影响 $(x,p_x)$ 答案的计算。

如果得到到达 $x$ 的时间集合 $T$，考虑如何计算 $(x,p_x)$ 的贡献。显然最后经过时刻具有单调性，考虑二分时间 $t$，判断能否再 $\le t$ 时间走完这条边。

考虑 hall 定理，相当于每个时刻 $t_i$ 可以连边 $(t_i,t]$，判断是否存在完美匹配。为了方便，平移一格匹配，也就是 $t_i$ 可以连边 $[t_i,t]$，将求出的时刻 $t$ 加一即可。只需要考虑所有后缀 $(i,t]$，是否都满足 $|N(S)|\ge |S|$，即 $t-i\ge s_{t}-s_{i}$，其中 $s_i$ 表示时刻小于等于 $i$ 的点的个数，条件等价于 $t-s_{t}\ge i-s_{i}$。

这个信息可以通过线段树合并维护区间 $\max\{i-s_i\}$，线段树上二分查询得到。

拓展到基环树上，考虑断环为链，就可以考虑到所有经过环上的路径了，注意到复制的环上的点会正确地考虑到所有信息。

注意到二分的位置需要包含所有子树中目前存在时刻，我先维护区间时刻出现次数和，求出但前最大时刻 $pos$，在 $[pos,+\infty)$ 上二分。

线段树合并需要进行区间修改，为了减少空间，我使用了标记永久化。

事实上观察到 $s_t$ 为定值，那么相当于 $i\ge j+s_{i}-s_{j}$，可以转化为单点修改，答案也是容易合并的。

代码写得很复杂，建议参考其他的题解。

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include <bits/stdc++.h>
#define file_in(x) (freopen(#x".in", "r", stdin))
#define file_out(x) (freopen(#x".out", "w", stdout))
#define vi vector
#define pr pair <int, int>
#define mk make_pair
#define pb push_back

using namespace std;

bool START;

const int N = 4e5 + 5, M = 100, inf = 1e9;

int n, m, p[N], a[N], b[N];
int stk[N], tot, vis[N];
int d[N], idx, dy[N];
int dfn[N], sz[N], tp[N], dep[N], mxd[N], cnt;
int v[N];
int fr[N], o;
int lim;

int rt[N], mx[N * M], ex[N * M], tag[N * M], ls[N * M], rs[N * M], num;
int ans;

vi <int> G[N], q, id[N];
vi <pr> vc[N];

bool END;

void add_e(int x, int y) {G[x].pb(y);}

void dfs(int x) {
  if (v[x]) {
    bool fl = 0;
    for (int i = 1; i <= tot; ++i) {
      if (stk[i] == x) fl = 1;
      if (fl) d[++idx] = stk[i];
    }
    return;
  }
  stk[++tot] = x, v[x] = 1, dfs(p[x]);
}

void dfs2(int x, int TP) {
  dfn[x] = ++cnt, sz[x] = 1, tp[x] = TP, fr[x] = o, q.pb(x);
  for (auto y : G[x]) if (!vis[y]) dep[y] = dep[x] + 1, dfs2(y, TP), sz[x] += sz[y];
}

void psu(int l, int r, int x) {
  int mid = (l + r) >> 1;
  mx[x] = max(ls[x] ? mx[ls[x]] : mid, rs[x] ? mx[rs[x]] : r) + tag[x];
  ex[x] = ex[ls[x]] + ex[rs[x]];
}

void work(int k, int p) {tag[p] -= k, mx[p] -= k;}

int nnd(int l, int r) {
  return num++, mx[num] = r, ls[num] = rs[num] = ex[num] = tag[num] = 0, num;
}

int mrg(int l, int r, int x, int y) {
  if (!x || !y) return x | y;
  tag[x] += tag[y];
  if (l == r)
    return mx[x] = r + tag[x], ex[x] += ex[y], x;
  int mid = (l + r) >> 1;
  ls[x] = mrg(l, mid, ls[x], ls[y]);
  rs[x] = mrg(mid + 1, r, rs[x], rs[y]);
  return psu(l, r, x), x;
}

void add(int l, int r, int L, int R, int k, int & p) {
  if (!p) p = nnd(l, r);
  if (l >= L && r <= R) return work(k, p);
  int mid = (l + r) >> 1;
  if (L <= mid) add(l, mid, L, R, k, ls[p]);
  if (R > mid) add(mid + 1, r, L, R, k, rs[p]);
  psu(l, r, p);
}

void addex(int l, int r, int ps, int k, int & p) {
  if (!p) p = nnd(l, r);
  if (l == r) return ex[p] += k, void();
  int mid = (l + r) >> 1;
  ps <= mid ? addex(l, mid, ps, k, ls[p]) : addex(mid + 1, r, ps, k, rs[p]);
  psu(l, r, p);
}

int getp(int l, int r, int p) {
  if (!ex[p]) return -1;
  if (l == r) return l;
  int mid = (l + r) >> 1;
  if (ex[rs[p]] > 0) return getp(mid + 1, r, rs[p]);
  return getp(l, mid, ls[p]);
}

int ask(int l, int r, int L, int R, int & premx, int k, int p) {
  int mid = (l + r) >> 1;
  if (!ls[p]) ls[p] = nnd(l, mid);
  if (!rs[p]) rs[p] = nnd(mid + 1, r);
  if (l >= L && r <= R) {
    if (l == r) {
      if (mx[p] + k >= premx) return l;
      return -1;
    }
    k += tag[p];
    if (mx[ls[p]] + k >= premx)
      return ask(l, mid, L, R, premx, k, ls[p]);
    else if (mx[rs[p]] + k >= (premx = max(premx, mx[ls[p]] + k)))
      return ask(mid + 1, r, L, R, premx, k, rs[p]);
    else premx = max(premx, mx[rs[p]] + k);
    return -1;
  }
  k += tag[p];
  if (L <= mid) {
    int t = ask(l, mid, L, R, premx, k, ls[p]);
    if (t != -1) return t;
  }
  premx = max(premx, mx[ls[p]] + k);
  return ask(mid + 1, r, L, R, premx, k, rs[p]);
}

void dfs3(int x) {
  mxd[x] = dep[x];
  for (auto y : G[x]) {
    if (x == d[1] + n && y == d[idx] + n) continue;
    if (x == d[1] && y == d[idx]) continue;
    dfs3(y);
    rt[x] = mrg(0, lim, rt[x], rt[y]), mxd[x] = max(mxd[x], mxd[y]);
  }
  for (auto [t, v] : vc[x]) {
    add(0, lim, t, lim, v, rt[x]);
    addex(0, lim, t, v, rt[x]);
  }
  int tmp = -inf, pos = getp(0, lim, rt[x]);
  if (pos != -1) {
    int tim = ask(0, lim, pos, lim, tmp, 0, rt[x]);
    ans = max(ans, tim - dep[x] + 1);
  }
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n; for (int i = 1; i <= n; ++i) cin >> p[i];
  cin >> m; for (int i = 1; i <= m; ++i) cin >> a[i] >> b[i], id[a[i]].pb(i);
  for (int i = 1; i <= n; ++i) if (!vis[i]) add_e(p[i], i), add_e(p[i] + n, i + n);
  lim = max(n, m) * 2 + 5;
  int fl = 1;
  for (int s = 1; s <= n; ++s) {
    if (v[s]) continue;
    idx = tot = cnt = num = 0, ++o, q.clear();
    dfs(s);
    for (int i = 1; i <= idx; ++i) {
      d[i + idx] = d[i] + n;
      dy[d[i]] = i, vis[d[i]] = 1;
      dy[d[i] + n] = i + idx, vis[d[i] + n] = 1;
    }
    add_e(d[idx + 1], d[idx]);
    for (int i = 1; i <= 2 * idx; ++i)
      dep[d[i]] = 2 * idx - i, dfs2(d[i], d[i]);

    for (int w : q) {
      for (auto i : id[w]) {
	if (fr[b[i]] != o) {fl = 0; break;}
	vc[a[i]].pb(mk(dep[a[i]], 1)), vc[a[i] + n].pb(mk(dep[a[i] + n], 1));
	if (vis[b[i]]) {
	  int l = dy[tp[a[i]]], r = dy[b[i]];
	  if (l <= r)
	    vc[b[i]].pb(mk(dep[a[i]], -1)), vc[b[i] + n].pb(mk(dep[a[i] + n], -1));
	  else vc[b[i] + n].pb(mk(dep[a[i]], -1));
	}
	else {
	  vc[b[i]].pb(mk(dep[a[i]], -1)), vc[b[i] + n].pb(mk(dep[a[i] + n], -1));
	  if (!(tp[a[i]] == tp[b[i]] && dfn[a[i]] >= dfn[b[i]] && dfn[a[i]] < dfn[b[i]] + sz[b[i]])) {
	    fl = 0; break;
	  }
	}
      }
    }
    if (!fl) return cout << -1 << endl, 0;
    dfs3(d[2 * idx]);
  }
  cout << ans << endl;
  return 0;
}