《wwx》的学习总结(题解)

《wwx》的学习总结(题解)WWX解题报告题目Description在美丽的双十中学里面,有一座高一学堂。所谓山不在高,有仙则名;水不在深,有龙则灵。双十信息组,因为有了wwx,就成了现在这个样子==。由于wwx的语言太过雷人,每次他发微往往都会有一石激起千层浪的效果,具体就是所有关注他的人都会转发,同时@他

大家好,欢迎来到IT知识分享网。《wwx》的学习总结(题解)"

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

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信