CodeForces 396C 树状数组 + DFS

本主题开始看到以为段树或树状数组，但是，对于一个节点的有疑问的所有子节点的加权，这一条件被视为树的根，像然后1号是肯定在第一层中，然后建立一个单向侧倒查，然后记录下来其中每个节点层，终于两个节点之间的差图层知道，上easy加权成交，然后，我们开始建立的数组，一直爆错，后来发现是范围有问题，这样直接建立是错的，由于不知道详细范围，数字太大了。所以參考了一下

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

相关文章