首页 > 其他分享 >HDU5593 ZYB's Tree

HDU5593 ZYB's Tree

时间:2022-09-02 22:24:16浏览次数:51  
标签:HDU5593 head ZYB int sum Tree ecnt fa 500005

求 \(n\) 个点的树上对于每个点距离小于 \(k\) 的点的数量(边权均为 \(1\) )。 \(n\leq 5\times 10^5,k\leq 10\) 。


设 \(f[u][i]\) 表示距离 \(u\) 点 \(i\) 距离以内并且在子树内的点,那么在 \(DFS\) 时可以用 \(O(nk)\) 的时间处理 \(f[u][i]=\sum f[v][i-1]\) ,其中 \(v\) 是 \(u\) 的孩子。

同理,设 \(g[u][i]\) 表示距离 \(u\) 点距离 \(i\) 以内并且在子树外(但包含自己)的点,这一项需要用父亲信息去更新儿子信息, \(g[u][i]=g[fa][i-1]\) ,同时可能会 \(u\rightarrow fa\rightarrow bro\) ,那么在 \(bro\) 的内部也可能会存在符合条件的点,所以 \(g[u][i]+=\sum f[bro][i-2]\) ,为了避免重复计算,可以在第一次 \(DFS\) 时在 \(fa\) 节点记录 \(sum[u][i]=\sum f[son][i]\) ,那么在调用时只用将 \(g[u][i]+=sum[fa][i-2]-f[u][i-2]\) 即可。

#include<bits/stdc++.h>
using namespace std;

int n,k,t;
struct edge{
    int to,nxt;
}e[500005];
int head[500005],ecnt;
void adde(int u,int v){
    e[++ecnt].to=v;
    e[ecnt].nxt=head[u];
    head[u]=ecnt;
}

int f[500005][15],g[500005][15],sum[500005][15];

void dfs1(int u,int fa){
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa)
            continue;
        dfs1(v,u);
        for(int j=1;j<=k;++j){
            f[u][j]+=f[v][j-1];
            sum[u][j]+=f[v][j];
        }
        sum[u][0]+=f[v][0];
    }
}

void dfs2(int u,int fa){
    if(fa){
        for(int i=1;i<=k;++i){
            g[u][i]+=g[fa][i-1];
        }
        for(int i=2;i<=k;++i){
            g[u][i]+=sum[fa][i-2]-f[u][i-2];
        }
    }
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa)
            continue;
        dfs2(v,u);
    }
}



int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&k);
        memset(head,0,sizeof head);
        memset(f,0,sizeof f);
        memset(g,0,sizeof g);
        memset(sum,0,sizeof sum);
        ecnt=0;
        long long A,B;
        scanf("%lld %lld",&A,&B);
        for(int i=2;i<=n;++i)
            adde((A*i+B)%(i-1)+1,i);
        for(int i=1;i<=n;++i){
            for(int j=0;j<=k;++j){
                f[i][j]=g[i][j]=1;
            }
        }
        dfs1(1,0);
        dfs2(1,0);
        int ans=0;
        for(int i=1;i<=n;++i)
            ans^=f[i][k]+g[i][k]-1;
        printf("%d\n",ans);
    }
    return 0;
}

标签:HDU5593,head,ZYB,int,sum,Tree,ecnt,fa,500005
From: https://www.cnblogs.com/zhouzizhe/p/16651533.html

相关文章

  • CF1491H Yuezheng Ling and Dynamic Tree
    传送门这真是一道分块神题!思路我们先将点编号进行分块令\(b[i]\)表示\(i\)的祖先中,最近的不与\(i\)同一个块的结点编号显然,如果\(pos[a[i]]<pos[i]\),那么\(b......
  • 27 | JAVA集合TreeMap(Map接口下除HashMap实现的另一种实现)
    TreeMap我们已经知道,HashMap是一种以空间换时间的映射表,它的实现原理决定了内部的Key是无序的,即遍历HashMap的Key时,其顺序是不可预测的(但每个Key都会遍历一次且仅遍历一次......
  • CF375E Red and Black Tree
    题目传送门Solution非常神奇的一道题。我们不考虑交换操作,相反,我们去考虑把多少个\(0\)的位置变为\(1\),同时我们记录选了多少个黑点,如果跟原来黑点数量相同即是合法......
  • element-ui tree权限树
    在权限中父子集不关联,一开始,我以为default-checked-keys值不对,最后看了文档,原来是check-strictly被开启了 <el-treeref="menu":......
  • CF620E NewYearTree
    题目链接  主要要实现区间覆盖和区间查询不同数,看见区间赋值操作可能会想到\(ODT\)来实现,区间查询不同数直接另外开一个数组记录一下就好了,但很可惜\(TLE\)了,代码如下:......
  • Vue中报npm WARN idealTree Removing dependencies.element-ui in favor of devDepend
    在添加element-ui的时候我是用的是:npmielement-ui--save-dev或npmielement-ui-S都会报错npmWARNidealTreeRemovingdependencies.element-uiinfavorofdevD......
  • C20220712T3 牛半仙的妹子Tree
    给定一棵树,要求执行3种操作:给树上某一结点涂色,从下一次操作起每一次向周围传染一个单位。树上所有点变为正常询问某个点是否被感染。\(n,m\leq10^5\)。首先想到暴......
  • LeetCode04. Maximum Depth of Binary Tree
    题意求一棵二叉树的深度方法DFS,更新当前最大深度代码voiddfs(TreeNode*root,int&height,int&ans){if(root==nullptr)return;height++;......
  • el-select和el-tree一起用
    html代码<el-form-itemlabel="树型结构"><el-selectv-model="treeData"placeholder="请选择..."style="width:16rem"><el-option:v......
  • VScode-TodoTree 待办事项插件的定制和使用
    VScode-TodoTree待办事项插件的定制和使用背景写代码过程中,突然发现一个Bug,但是又不想停下来手中的活,以免打断思路,怎么办?按代码编写会规范,都是建议在代码中加个TODO......