大家好，欢迎来到IT知识分享网。
WWX 解题报告
题目
Description
在美丽的双十中学里面，有一座高一学堂。所谓山不在高，有仙则名；水不在深，有龙则灵。双十信息组，因为有了 wwx，就成了现在这个样子 = =。 由于wwx 的语言太过雷人，每次他发微往往都会有一石激起千层浪的效果，具体就是所有关注他的人都会转发，同时@他，接着关注这些人的人也会转发，同时@他关注的人（注意转发内容本身会有@wwx ），以此类推。这样导致每次 wwx 发微博都会被@上兆次，而 wwx又特别喜欢发，sina支持不了如此庞大的数据量，特出规定，每次转发时，@的人不能超过 K 人，好友在转发时如果超过了，就把最早那人删掉。现在 wwx 刚发了一条微博“求 AK”，他想知道每个与他有联系的人分别会被@多少次。
Output Format
输出有N行，每行有一个整数，这个人会被@多少次。
Sample Input
5 2 1 2 2 3 2 4 4 5
Sample Output
3
3 0 1 0
概括
意思就是说，让你求出每个节点，往下数k层有几个子节点
不多说，程序里面解释
//这题是树上差分， 加上栈的思想 //巧妙利用搜索中压栈的思想 #include<bits/stdc++.h> using namespace std; long long head[1010010], cnt, ans[1000101]; struct Ed{ int to, ne; }edge[1001010]; void addedge(int u, int v) { edge[++ cnt].ne = head[u]; edge[cnt].to = v; head[u] = cnt; } int n, k; long long dep[1001010], son[1001010]; long long st[1001001], top; void dfs(int x, int fa) { son[x] = 1;//自己设为1 st[++ top] = x;//将当前搜索到的这个点压入栈中 for (int i = head[x]; i; i = edge[i].ne) { if (edge[i].to == fa) continue; dep[edge[i].to] = dep[x] + 1;//记录dep dfs(edge[i].to, x); son[x] += son[edge[i].to];//自下而上统计每个点的儿子数 //注意这里统计儿子一定要自下而上，因为要把当前这个点搜到头后 //才能记录下这个点所有的儿子数 } ans[x] += son[x] - 1;//首先将答案ans加上这个点的儿子数减1 if (top > k + 1) ans[st[top - k - 1]] -= son[x]; //如果当前这个ansx的儿子数大于了k个，就要舍去，那么将它上面k层的那个点 //减去这个点及其以下的儿子数 -- top;//弹出栈 } int main() { cin >> n >> k; for (int i = 1; i < n; i ++) { int x, y; scanf("%d %d", &x, &y); addedge(x, y); addedge(y, x); } dfs(1, 0); for (int i = 1; i <= n; i ++) printf("%lld\n", ans[i]); return 0; }
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/31375.html
