题目大意:给定一个树,每个节点都有一个权值,给定一个值k,有q次询问,试求以节点x为根的子树中每个节点的权值数相同恰好出现k次的数目。
组队训练的时候,钢牛和冰姐都没有研究这道题,我还看错了一次,反正是比赛的时候没有什么思路的啊!
解题思路:将树装换为线性数组,然后记录其子树所在线性数组的左右区间,所以每次询问的时候就是一个给定的l和r值,进行更新而已。
对于每次的询问进行r从小到大进行排序,遍历线性数组,对于第i个数x,如果还没有出现k次则不操作,若恰好出现k次,则对其第0出现所在的位置进行+1,更新操作,如果出现大于k次,假设出现了n次,则对其n-k-1进行-2的更新操作,因为一个-1是为了抵消之前为k时加的1,还有一个是为了当l小于次值时进行抵消的,然后对于n-k进行+1更新操作,对于每次询问,结果为sum(r)-sum(l-1);
下面是代码:
#pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<queue> #include<map> using namespace std; #define rep(i,n) for(int i=0; i<(n); ++i) #define repf(i,n,m) for(int i=(n); i<=(m); ++i) #define repd(i,n,m) for(int i=(n); i>=(m); --i) #define N 100005 int v[N]; int g[N]; vector<int>vec[N]; int n,m,len,q; int lson[N],rson[N]; int b[N]; int dp[N]; int ans[N]; struct node{ int l,r,i; }; node a[N]; void dfs(int s,int fa)//l和r分别指的是问的数的左右的 { lson[s]=rson[s]=len++; b[s]=v[s-1];//一个从1开始的,一个从0开始的 rep(i,vec[s].size()) { int y=vec[s][i]; if(y==fa) continue; dfs(y,s); rson[s]=rson[y]; } } bool cmp(const node a,const node b) { return a.r<b.r; } int lowbit(int x) { return x&(-x); } void update(int x,int l) { for(;x<=n; x+=lowbit(x)) dp[x]+=l; } int sum(int x) { int ans=0; for(; x>0; x-=lowbit(x)) ans+=dp[x]; return ans; } int main() { int test; scanf("%d",&test); int x,y; repf(ror,1,test) { memset(dp,0,sizeof(dp)); scanf("%d%d",&n,&m); rep(i,n) scanf("%d",&v[i]),g[i]=v[i]; //数值进行离散化的 sort(g,g+n); int pl=unique(g,g+n)-g; rep(i,n) v[i]=lower_bound(g,g+pl,v[i])-g; //线性化的 repf(i,0,n) vec[i].clear(); rep(i,n-1) scanf("%d%d",&x,&y), vec[x].push_back(y), vec[y].push_back(x); len=1;//记录的东西的啊 dfs(1,-1); scanf("%d",&q); rep(i,q) { scanf("%d",&x); a[i].l=lson[x]; a[i].r=rson[x]; a[i].i=i; } sort(a,a+q,cmp); repf(i,0,n) vec[i].clear(); int l=0; repf(i,1,n) { int y=b[i]; vec[y].push_back(i); if(vec[y].size()>=m) { //如果相等的话就前面的加1的 if(vec[y].size()==m) update(vec[y][0],1); else //如果大于的话,就需要进行减去操作,还要减去之前减2的 update(vec[y][vec[y].size()-m-1],-2), update(vec[y][vec[y].size()-m],+1); } while(a[l].r==i && l<n) ans[a[l].i]=sum(a[l].r)-sum(a[l].l-1), l++; if(l==n) break; } printf("Case #%d:\n",ror); rep(i,q) printf("%d\n",ans[i]); if(ror!=test) printf("\n"); } return 0; }
最近为区域赛做准备,已经开始组队训练,和钢牛和冰姐组队,钢牛的能力很强,只不过最近状态不是怎么好啊!冰姐是乐天派,可以带动气氛,并且怎么说都比我厉害,我本来就很想和他们两个,貌似有点抱大腿哎!算了,废话不多说,做好自己的就高兴了,是不?