网站推广的技术,广告设计专业哪个大学最好,网页设计编辑器,推广和竞价代运营原题链接#xff1a; https://acm.hdu.edu.cn/showproblem.php?pid5927
题意#xff1a; 有一颗根节点是1的树#xff0c;其中有重要的点和不重要的点#xff0c;重要的点需满足以下两个条件至少一个#xff1a; 1.本来就是重要的点 2.是两个重要的点的最近共同祖先 有t…原题链接 https://acm.hdu.edu.cn/showproblem.php?pid5927
题意 有一颗根节点是1的树其中有重要的点和不重要的点重要的点需满足以下两个条件至少一个 1.本来就是重要的点 2.是两个重要的点的最近共同祖先 有t个测试实例对于每个测试实例 给出结点个数n和询问次数q 对于每次询问 给出一个数con表示不重要的点的个数 接下来con个数是不重要的点的编号 对于每个询问求出重要的点的个数每次询问之间相互独立
思路 ans记录重要结点的个数 本来就是重要的点有n-con个 那么我们就需要检查一下不重要的点对于每个不重要的点看看他是不是两个重要的点的最近共同祖先
对于点u如果他的以儿子结点为根的子树中多于两个子树里有 重要的结点那么u就能变成重要的结点
那么我们可以先预处理好每个结点的儿子结点的个数每个点的父节点和每个点的深度
然后再对不重要的结点按照深度从大到小的顺序排序
从最深的结点u开始遍历如果u的有重要点的儿子结点数量超过两个那么u就可以变成重要结点ans
如果变不了重要结点说明u的有重要点的儿子结点数量要么是0要么是1如果是0那么u的父节点的有重要儿子结点的数量就需要-1因为每次询问独立那么我们需要将减掉的点给记录一下当这次询问完毕时再复原加上
#include bits/stdc.h
using namespace std;
const int maxn1e55;
int d[maxn];
int book[maxn];
vectorint edg[maxn];
int que[maxn];
int impor[maxn];
int unimpor[maxn];
int ans;
int son[maxn];
int so[maxn];
int fa[maxn];
bool cmp(int x, int y)
{return d[x]d[y];
}
void dfs(int x, int y)
{fa[x]y;son[y];son[x]0;d[x]d[y]1;for(int i0; i(int)edg[x].size(); i){if(edg[x][i]!y)dfs(edg[x][i],x);}return;
}
int main()
{int t;cint;int e1; while(t--){int n;int q;scanf(%d%d, n, q);int i, j, x, y;for(i0; in-1; i){scanf(%d %d, x, y);edg[x].push_back(y);edg[y].push_back(x); }dfs(1,0);int m;printf(Case #%d:\n, e); while(q--){scanf(%d, m);for(i0; im; i){ scanf(%d, unimpor[i]);//不重要节点so[unimpor[i]]son[unimpor[i]];//节点的儿子}ansn-m;sort(unimpor, unimporm, cmp);for(i0; im; i){if(so[unimpor[i]]2)ans;else{if(so[unimpor[i]]0) so[fa[unimpor[i]]]--;}}printf(%d\n, ans);}for(i1; in; i){edg[i].clear();
// vectorint().swap(edg[i]);}}
}
