网站title设置,网站seo具体怎么做?,西宁制作网站多少钱,2022年卡一卡二卡三精品题干#xff1a;
给出一个n1个点的树#xff0c;以及p个点对#xff0c;需要断开一些点#xff0c;使得这p个点对路径不连通。输出应该断开的最少点数。
解题报告#xff1a;
从那p个点对入手的话#xff1a;首先考虑只有一对点的话#xff0c;肯定是这条路径上的随便…题干
给出一个n1个点的树以及p个点对需要断开一些点使得这p个点对路径不连通。输出应该断开的最少点数。
解题报告
从那p个点对入手的话首先考虑只有一对点的话肯定是这条路径上的随便一个点都可以。两个点对呢肯定是有交点就选交点没交点就只能破坏两个点了。多个点对呢比较难考虑了。也比较难想到正解贪心思维破坏两个点的LCA是最佳的。
从破坏的点入手破坏一个点可以影响到的是所有经过他的所有的路径转化到有根树中不难想到这个点就是lca。
当然这个题到这里还不够还需要加点贪心的思想对p个点对按照他们的lca深度从大到小排序如果某个点需要被破坏那么它的所有子节点子树都可以不再需要破坏别的点了因为它的子节点到别的子节点肯定是要经过该点的要注意这个前提是lca是排好序的。所以对应的操作就是对子树的所有节点都1。
为什么要排序呢因为这样就能保证当前处理到第i对点u,v如果这个点所在任意子树的某祖先x如果有被标记过那么这条路径一定就不用管了因为uv的lca一定深度小于x也就是说你u想到达v一定要经过x又因为x已经被破坏了所以这对点直接不用管了真神奇的想法
所以接下来问题就是判断现在在u,v之间的路径上有没有被破坏的点也就是查询u和v这两点的值是不是0的如果没有的话那么此时就要破坏这个lca点如果有的话就直接continue。
所以dfs序来维护子树然后用树状数组差分来维护区间和查询的时候查询单点值。当然这后一步可以直接用线段树来取代
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e4 5;
int n,in[MAX],out[MAX],clk,dep[MAX],id[MAX],c[MAX*10];
int fa[MAX][33];
vectorint vv[MAX];
struct Node {int a,b,lca;bool operator (const Node bb)const {return dep[lca] dep[bb.lca];}
} p[MAX*5];
int lowbit(int x){ return x(-x); }
int query(int pos) {int res 0;while(pos 0) {res c[pos];pos - lowbit(pos);}return res;
}
void update(int pos,int val) {while(pos MAX) {c[pos] val;pos lowbit(pos);}
}
void dfs(int cur,int rt,int deep) {in[cur] clk;dep[cur] deep;fa[cur][0]rt;id[clk] cur;int up vv[cur].size();for(int i 1; i31; i) {fa[cur][i] fa[fa[cur][i-1]][i-1];}for(int i 0; iup; i) {int v vv[cur][i];if(v rt) continue;dfs(v,cur,deep1);}out[cur] clk;
}
int lca(int u,int v) {if(dep[v] dep[u]) swap(u,v);for(int i 31; i0; i--) {if(dep[fa[u][i]] dep[v]) u fa[u][i];}if(u v) return u;for(int i 31; i0; i--) {if(fa[u][i] ! fa[v][i]) u fa[u][i],vfa[v][i];}return fa[u][0];
}
int main()
{while(~scanf(%d,n)) {int a,b;clk0;memset(fa,0,sizeof fa);memset(c,0,sizeof c);for(int i 0; in1; i) vv[i].clear();for(int i 1; in; i) {scanf(%d%d,a,b);a,b;vv[a].pb(b);vv[b].pb(a);}dfs(1,0,1);int q;scanf(%d,q);for(int i 1; iq; i) {scanf(%d%d,a,b);a,b;p[i].a a,p[i].b b,p[i].lca lca(a,b);}sort(p1,pq1);int ans 0;for(int i 1; iq; i) {if(query(in[p[i].a]) query(in[p[i].b]) 0) {ans;update(in[p[i].lca],1);update(out[p[i].lca]1,-1);}}printf(%d\n,ans);}return 0 ;
}
