asp网站后台验证码错误/百度推广方案怎么写

题意

T个样例，n个点，q次查询。每次查询包含m和m个数字，m个数字表示不重要点的编号。规定两个重要的点的最近公共祖先也是重要的点。求树中重要的点的个数。

题解

重要的点包含原始重要点和公共祖先点，原始重要点为n-m。对于公共祖先点，我们可以首先对不重要的点按深度从大到小进行排序。然后从大到小进行遍历，如果该点有两个重要子节点，则该点为重要点，重要点数量++。如果该点没有重要子节点，则该点无法为父节点贡献重要子节点，因此父节点的重要子节点数目需要减一。完成遍历，即可得到树中重要点的个数。

注意事项

注意边最多可能有1e5*2条，因此边数组至少需要开1e5*2个。

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define MAXN 100010using namespace std;
int head[MAXN],deep[MAXN],son[MAXN],fa[MAXN],a[MAXN],cnt[MAXN];
int pos;
struct {int to,next;
}edge[MAXN*2];void addEdge(int u,int v){edge[pos].to=v;edge[pos].next=head[u];head[u]=pos++;
}bool cmp(int a,int b){return deep[a]>deep[b];
}void dfs(int u,int f){son[u]=0;fa[u]=f;//printf("%d %d ",u,f);for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(v==f)continue;son[u]++;deep[v]=deep[u]+1;dfs(v,u);}
}void init(){memset(son,0,sizeof(son));memset(fa,0,sizeof(fa));memset(head,-1,sizeof(head));memset(deep,0,sizeof(deep));
}int main(){int t;scanf("%d",&t);for(int ks=1;ks<=t;ks++){pos=0;printf("Case #%d:\n",ks);init();int n,q;scanf("%d%d",&n,&q);for(int i=0;i<n-1;i++){int a,b;scanf("%d%d",&a,&b);addEdge(a,b);addEdge(b,a);}dfs(1,0);for(int i=0;i<q;i++){int m;scanf("%d",&m);for(int j=0;j<m;j++){scanf("%d",&a[j]);}sort(a,a+m,cmp);int ans=n-m;for(int j=0;j<m;j++){cnt[a[j]]=son[a[j]];}for(int j=0;j<m;j++){if(cnt[a[j]]>=2)ans++;if(cnt[a[j]]==0)cnt[fa[a[j]]]--;}printf("%d\n",ans);}}
}