首页 > 代码库 > CodeForces 396C 树状数组 + DFS
CodeForces 396C 树状数组 + DFS
这题目一开始看到了就想到了线段树或者树状数组,但是对于一个节点的所有子节点加权有所疑惑,后来看到根树这个条件,就像到了 那么1号点肯定在第一层,那么建立单向边往下搜,然后记录一下 每一个节点所在的 层,最后 两个节点 相差的 层数就知道了,就容易加权处理了,然后就开始建立数组了,后来一直爆错,后来发现 是范围有问题,这样直接建立是错的,因为不知道具体范围,数字太大了, 所以参考了一下
http://blog.csdn.net/keshuai19940722/article/details/20128965
厉害啊,我想不到,原来可以建立两个树状数组,然后 在深搜找出节点所在层的同时 也记录一下 它的时间戳,也就是这个节点第一次被访问到的作为一个记录和的树状数组下标,以及往下找子节点回溯回来的这个时间错 建立另一个记录要减去的和的树状数组下标,这样范围就确定了,但是这样无法直接加权,要对 第一次访问到的 加权 然后对 回溯的 进行同样的值的 负值加权,同时加权的时候 直接全部都加上去,不考虑节点与此时父节点相差层数,只考虑与根的,然后 这样是多加了的,这时候 可以把要减去的 给算好,最后一起减去就可以了,要减去的 就直接加上 k,最后一起算的时候 再乘上与根 相差层数,两个树状数组都以与主根 相差层数为基准,这样 就可以了
然后这个取余不知道怎么了,一直WA,后来我手写了一个 MODE函数才过,原来直接取模 我也考虑了负数 要多加一个MOD但是 还是WA,为什么别人可以 我就不行了 郁闷
#define MOD 1000000007 int n,tot; int vis[300000 + 55]; int le[300000 + 55],ri[300000 + 55]; ll ad[300000 + 55],sub[300000 + 55]; vector<int > G[300000 + 55]; void init() { for(int i=0;i<300000 + 55;i++)G[i].clear(); memset(vis,0,sizeof(vis)); memset(ad,0,sizeof(ad)); memset(sub,0,sizeof(sub)); memset(le,0,sizeof(le)); memset(ri,0,sizeof(ri)); tot = 0; } bool input() { while(cin>>n) { for(int i=2;i<=n;i++) { int x; scanf("%d",&x); G[x].push_back(i); } return false; } return true; } void dfs(int u,int cnt) { tot++; le[u] = tot; for(int i=0;i<G[u].size();i++) { int v = G[u][i]; dfs(v,cnt + 1); } vis[u] = cnt; ri[u] = tot; } ll MODE(ll x) { if(x >= MOD)x %= MOD; else if(x < 0ll)x = (x + MOD)%MOD; return x; } int lowbit(int x) { return x&(-x); } void add1(int i, ll val) { while (i <= tot) { ad[i] += val; ad[i] = MODE(ad[i]); i += lowbit(i); } } void add2(int i,ll val) { while(i <= tot) { sub[i] += val; sub[i] = MODE(sub[i]); i += lowbit(i); } } ll get_sum1(int i) { ll sum = 0; while (i > 0) { sum += ad[i]; sum = MODE(sum); i -= lowbit(i); } return sum; } ll get_sum2(int i) { ll sum = 0ll; while(i > 0) { sum += sub[i]; sum = MODE(sum); i -= lowbit(i); } return sum; } void cal() { dfs(1,0); int q; cin>>q; while(q--) { int type; scanf("%d",&type); if(type == 1) { int v; ll x,k; scanf("%d %I64d %I64d",&v,&x,&k); x = (x + (vis[v] - 1) * k)%MOD; add1(le[v],x); add1(ri[v] + 1,-x); add2(le[v],k); add2(ri[v] + 1,-k); } else { int v; scanf("%d",&v); ll xx = get_sum1(le[v]); ll yy = get_sum2(le[v]); ll ans = MODE(xx - MODE((vis[v] - 1) * yy)); printf("%I64d\n",ans); } } } void output() { } int main() { while(true) { init(); if(input())return 0; cal(); output(); } return 0; }
CodeForces 396C 树状数组 + DFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。