网站页脚怎么做美观,企业网站源码带手机版,中国铁路建设集团公司网站,网站开发 渠道problem
洛谷链接
solution
考虑重新随便钦定一个点为“根”#xff0c;并且强制根必须是关键点。
则所有 x−yx-yx−y 不是直系祖先-子代的要求#xff08;要求Ⅰ#xff09;#xff0c;即 xxx 不是 yyy 祖先#xff0c;yyy 也不是 xxx 祖先#xff0c;一定都被满足…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 300005
vector 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;
}
