【XJOI】高一学堂

高一学堂"/>

【XJOI】高一学堂

题目链接

高一学堂

题目描述：

在美丽的中山纪念中学里面，有一座高一学堂。所谓山不在高，有仙则名；水不在深，有龙则灵。高一学堂，因为有了yxr，就成了现在这个样子 = =。由于yxr 的语言太过雷人，每次他发微往往都会有一石激起千层浪效果，具体就是所有关注他的人都会转发，同时@他，接着关注这些人的人也会转发，同时@他关注的人（注意转发内容本身会有@yxr），以此类推。这样导致每次yxr 发微博都会被@上兆次，而yxr 又特别喜欢发，sina 支持不了如此庞大的数据量，特出规定，每次转发时，@的人不能超过\(K\)人，好友在转发时如果超过了，就把最早那人删掉。现在yxr 刚发了一条微博“求满分”，他想知道每个与
他有联系的人分别会被@多少次。

输入格式：

输入第一行有三个整数,\(N\),\(K\)，表示人数和\(K\)。
接下来\(N-1\) 行，每行有2 个整数\(a\)，\(b\)，表示\(a\) 和\(b\) 有关注关系。
输入给出一棵以1 号点为根的树，一号点代表yxr，对于任意一个点，他的
儿子都关注他。

输出格式：

输出有\(N\) 行，每行有一个整数，这个人会被@多少次。

样例输入：

5 2
1 2
2 3
2 4
4 5

样例输出：

3
3
0
1
0

数据范围：

对于30%的数据，\(N≤100\)；
对于60%的数据，\(N≤2000\)，\(K≤100\)；
对于100%的数据，\(N≤100000\), \(K≤N\)。

时间限制：

1S

空间限制：

256M

提示：

remove!!!

题解

将题意简化后就是一棵树上每个节点都能给他的\(K\)次以内的父亲增加一个权值。
那么只要将一个节点作为根的那棵子树的大小减去所有距离他\(K+1\)的孩子的子树大小就是这个节点的答案了。
那么我们搜索两遍就好了，第一遍求出每个节点的子树大小，第二次遍历把每个节点的第\(K+1\)次父亲的\(ans\)减去当前节点。
注意：根据题意，自己是不能@自己的，所以\(ans\)要在子树大小的基础上减一。
时间复杂度为\(O(n)\)。
上代码：

#include<bits/stdc++.h>
using namespace std;
int n,lk;
int a,b;
struct aa{int to,nxt;
}p[200009];
int ans[100009],dis[100009];
int l,h[100009];
int uu[100009],len;
bool k[100009];
void add(int x,int y){l++;p[l].to=y;p[l].nxt=h[x];h[x]=l;
}
void dfs1(int x,int d){k[x]=1;dis[x]=1;for(int j=h[x];j;j=p[j].nxt)if(k[p[j].to]==0){dfs1(p[j].to,d+1);dis[x]+=dis[p[j].to];}k[x]=0;
}
void dfs2(int x,int d){if(d>lk+1) ans[uu[len-lk]]-=dis[x];k[x]=1;uu[++len]=x;for(int j=h[x];j;j=p[j].nxt)if(k[p[j].to]==0)dfs2(p[j].to,d+1);len--;k[x]=0;
}
int main(){scanf("%d%d",&n,&lk);for(int j=1;j<n;j++){scanf("%d%d",&a,&b);add(a,b);add(b,a);}dfs1(1,1);for(int j=1;j<=n;j++)ans[j]=dis[j]-1;dfs2(1,1);for(int j=1;j<=n;j++)printf("%d\n",ans[j]);return 0;
}

转载于:.html