CF375D Tree and Queries（dsu on tree）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

思路

dsu on tree的板子，可惜人傻把

for(int i=fir[u];i;i=nxt[i])


打成

for(int i=fir[u];i<=n;i++)


调了两个小时

这题要求维护>=k的颜色数量

所以考虑什么情况下会对答案产生贡献

显然是>=k的点数会产生贡献，所以用VAL记录每个颜色的出现次数，然后额外开一个d[k]数组表示>=k的颜色数量

然后就可以优雅的跑过去了

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int sz[100100],val[100100],heason[100100],u[100100<<1],v[100100<<1],w_p[100100],fir[100100],nxt[100100<<1],d[100100],vis[100100],cnt,n,m,ans[100100];
struct query{
int num,ansid;
};
vector<query> Q[100100];
void addedge(int ui,int vi){
++cnt;
u[cnt]=ui;
v[cnt]=vi;
nxt[cnt]=fir[ui];
fir[ui]=cnt;
}
void dfs1(int u,int f){
sz[u]=1;
for(int i=fir[u];i;i=nxt[i]){
if(v[i]==f)
continue;
dfs1(v[i],u);
sz[u]+=sz[v[i]];
if(heason[u]==0||sz[heason[u]]<sz[v[i]])
heason[u]=v[i];
}
}
void solve(int u,int f,int c){
if(c==-1)
d[val[w_p[u]]]+=c;
val[w_p[u]]+=c;
if(c==1)
d[val[w_p[u]]]+=c;
for(int i=fir[u];i;i=nxt[i]){
if(v[i]==f||vis[v[i]])
continue;
solve(v[i],u,c);
}
}
void dfs2(int u,int f,int islight){
for(int i=fir[u];i;i=nxt[i]){
if(v[i]==f||v[i]==heason[u])
continue;
dfs2(v[i],u,1);
}
if(heason[u])
dfs2(heason[u],u,0),vis[heason[u]]=true;
solve(u,f,1);
for(int i=0;i<Q[u].size();i++)
ans[Q[u][i].ansid]=d[Q[u][i].num];
if(heason[u])
vis[heason[u]]=false;
if(islight)
solve(u,f,-1);
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&w_p[i]);
for(int i=1;i<n;i++){
int x,y;
scanf("%d %d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for(int i=1;i<=m;i++){
query x;
int u;
scanf("%d %d",&u,&x.num);
x.ansid=i;
Q[u].push_back(x);
}
dfs1(1,0);
dfs2(1,0,1);
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}