BYR Achieve · 镜像论坛

传送门 http://acm.hdu.edu.cn/showproblem.php?pid=5927 解释一下题意就是这样的：给你一棵树，1为根，然后选择一部分点叫做“重要点”；定义“重要点集合”是这样的点：（1）重要点属于重要点集；（2）两个重要点的最近公共祖先属于重要点集；然后给你q次询问，每次询问输入一些“非重要点”，然后输出重要点集合有几个点？ ``` #include <bits/stdc++.h> using namespace std; typedef long long ll; int T; int n,q,u,v,mi; vector<int> g[100005]; int fa[100005]; int dp[100005]; int dp2[100005]; int m[100005]; int deep[100005]; int imp[100005]; int ans; void dfs(int u,int par,int d) { deep[u]=d; if(!fa[u]) fa[u]=par; for(int i=0;i<g[u].size();i++) { int v=g[u][i]; if(!fa[v]) { dfs(v,u,d+1); dp[u]++; } } } bool cmp(int x,int y) { return deep[y]<deep[x]; } void solve() { sort(m,m+mi,cmp); for(int i=0;i<mi;i++) { int u=m[i]; if(dp2[u]==0)//u点非重要且u点的孩子没有重要点 dp2[fa[u]]--; } for(int i=0;i<mi;i++) { int u=m[i]; if(dp2[u]>=2) ans++; } // for(int i=1;i<=n;i++) { // printf("dp2[%d] = %d\n", i,dp2[i]); // } } int main() { scanf("%d",&T); for(int t=1;t<=T;t++) { scanf("%d %d",&n,&q); memset(fa,0,sizeof(fa)); memset(dp,0,sizeof(dp)); memset(deep,0,sizeof(deep)); memset(g,0,sizeof(g)); for(int i=0;i<n-1;i++) { scanf("%d %d",&u,&v); g[u].push_back(v); g[v].push_back(u); } dfs(1,-1,0);//确定父子关系和深度 // for(int i=1;i<=n;i++) { // printf("fa[%d] = %d,dp[%d] = %d\n", i,fa[i],i,dp[i]); // } printf("Case #%d:\n",t); while(q--) { memset(m,0,sizeof(m)); memset(imp,0,sizeof(imp));//都是非重要的 scanf("%d",&mi); for(int i=0;i<mi;i++) { scanf("%d",&m[i]); //imp[m[i]]=1; } for(int i=0;i<mi;i++) dp2[m[i]]=dp[m[i]]; ans=n-mi; solve(); printf("%d\n", ans); } } } ``` 这段代码提交一直T，网上搜到的题解的AC代码如下： ``` #include <bits/stdc++.h> using namespace std; const int N=1e5+5; int L[N]; int cnt[N]; int tail; vector<int> g[N]; int par[N]; void dfs(int u, int f){ L[u]=++tail; par[u]=f; for(auto v: g[u]){ if(v!=f){ ++cnt[u]; dfs(v, u); } } } bool cmp(int x, int y){ return L[x]>L[y]; } vector<int> a; // unimportant nodes int _cnt[N]; // bool flag[N]; int main(){ int T, cas{}; for(cin>>T; T--; ){ int n, q; cin>>n>>q; for(int i=1; i<=n; i++){ g[i].clear(); cnt[i]=0; // error-prone } for(int i=1; i<n; i++){ int u, v; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } tail=0; dfs(1, 0); printf("Case #%d:\n", ++cas); for(; q--; ){ int m; cin>>m; a.clear(); for(; m--; ){ int x; scanf("%d", &x); a.push_back(x); // flag[x]=true; } sort(a.begin(), a.end(), cmp); for(auto x: a){ _cnt[x]=cnt[x]; } for(auto x: a){ if(_cnt[x]==0){ --_cnt[par[x]]; } } int res=0; for(auto x: a){ res+=_cnt[x]>=2; // _cnt[x]=cnt[x]; } res += n-a.size(); printf("%d\n", res); } } return 0; } ``` 看了一下午也没看出来我跟他写的有何区别，主要区别就是他没有我用这么多全局变量。但我记得全局区速度更快的呀，为什么他能ac我就T。跪求大神指教~~

[问题]请教杭电5927题，为什么一直在T？