problem

洛谷链接

solution

考虑重新随便钦定一个点为“根”，并且强制根必须是关键点。

则所有 x−yx-yx−y 不是直系祖先-子代的要求（要求Ⅰ），即 xxx 不是 yyy 祖先，yyy 也不是 xxx 祖先，一定都被满足。

所有 x−yx-yx−y 是直系祖先-子代的要求（要求Ⅱ）都不能被满足。根离这条路径最近的点一定是 x/yx/yx/y 中某个端点。

下面不妨仍认为 111 为根。考虑怎么才能最少且满足所有的要求Ⅱ。

采用延迟贪心的思想。从下往上考虑尽量晚放关键点（最浅化关键点的深度）。

感性想想这确实是最优的

到这里都是基于根被选为关键点的后续操作，但是这个根一定要成为关键点吗？

也有可能存在，考虑要求Ⅱ的时候，晚放的某些关键点恰好把所有的要求Ⅰ也顺带解决了的情况。

所以延迟贪心后，又反过来考虑是否要新增一个根为关键点，增加 111 的贡献。

换言之，在强制根的想法上找到了解法发现可行，现在回来再考虑假设的必要性。

发现，如果为了解决要求Ⅱ而放置的关键点无法解决要求Ⅰ，则要求Ⅰ的 lca\text{lca}lca 一定深度更小 / 这个关键点一定在要求Ⅰ的某个端点子树内。

只要有一个要求Ⅰ无法被满足，都意味着这个根作为关键点是必需的。

dfs树，利用 dfndfndfn 序，用树状数组维护关键点的信息即可。

注意：虽然之前说随便找个点做根，但这只是一种思考方式，并不是真的在代码中进行换根操作。

code

#include <bits/stdc++.h>using namespace std;#define maxn 300005vector < pair < int, int > > MS;vector < int > G[maxn], E[maxn];int n, m, cnt;int dep[maxn], L[maxn], R[maxn], t[maxn], id[maxn];int f[maxn][20];void dfs( int u ) {for( int i = 1;i < 20;i ++ ) f[u][i] = f[f[u][i - 1]][i - 1];L[u] = ++ cnt;for( int v : G[u] ) {dep[v] = dep[u] + 1;dfs( v );}R[u] = cnt;}int lca( int x, int d ) {for( int i = 19;~ i;i -- ) if( d >> i & 1 ) x = f[x][i]; return x; }void Add( int i ) {for( ;i <= n;i += i & -i ) t[i] ++; }int Ask( int i ) {int ans = 0; for( ;i;i -= i & -i ) ans += t[i]; return ans; }int get( int x ) {return Ask( R[x] ) - Ask( L[x] - 1 ); }int main() {scanf( "%d %d", &n, &m );for( int i = 2;i <= n;i ++ ) {scanf( "%d", &f[i][0] );G[f[i][0]].push_back( i );}dfs( 1 );for( int i = 1, u, v;i <= m;i ++ ) {scanf( "%d %d", &u, &v );if( dep[u] > dep[v] ) swap( u, v );if( f[v][0] == u ) return ! printf( "-1\n" );E[u].push_back( v );}iota( id + 1, id + n + 1, 1 );sort( id + 1, id + n + 1, []( int x, int y ) {return dep[x] > dep[y]; } );int ans = 0;for( int i = 1;i <= n;i ++ ) {int x = id[i];for( int y : E[x] ) {if( dep[x] == dep[y] ) MS.push_back( {x, y } ); //两个深度一样则一定隶属于不同子树else {int z = lca( y, dep[y] - dep[x] - 1 ); //爬到深度比x深1的祖先点if( f[z][0] ^ x ) MS.push_back( {x, y } ); //证明x,y不属于同一个子树else {if( get( z ) - get( y ) ) continue; //祖先-子代关系 判断x-y这条链(除了x,y)有没有关键点存在else ans ++, Add( L[z] );//新增关键点}}}}for( int i = 0;i < MS.size();i ++ ) {int x = MS[i].first, y = MS[i].second;if( get( x ) + get( y ) == ans ) {ans ++; break; } //判断x,y子树包含了所有的关键点，那么这个x-y旁系祖先-子代关系就必须通过根来满足了}printf( "%d\n", ans );return 0;}