标题效果：鉴于一棵树。每个节点有一个右值，所有节点正确启动值他们是0。有两种操作模式，0 x y代表x右所有点的子树的根值添加y。

1 k a1 b1 a2 b2 ……ak bk代表质疑。

共同拥有者k边缘( k <= 5)，这些边保证是一个点到根节点的路径上的一段。

问这些路径段上的点的权值和是多少，可能有多条路径重叠的情况。

思路：子树改动，区间查询，非常明显用树链剖分解决，树链剖分维护一个size域。那么x的子树的范围就是pos[x]到pos[x] + size[x] - 1这一段上。能够用线段树区间改动。

关键是查询的时候。单查一条链肯定没什么问题。

可是假设几条链有交集的话就麻烦了。可是依据容斥原理我们知道，当我们把全部的路径都加过一次之后，两个路径重合的部分就计算重了。减掉。之后三个路径重合的部分减多了。再加上……我们仅仅要求出单个链的，两个路径重合的部分，三个路径重合的部分……这样就能够知道答案了。

怎样求多个链相交呢？我们先考虑两个链相交。因为每个路径保证是一个点到根节点的路径上的一段，那么两个链相交仅仅有一种情况。

例如以下图。

链1 2 3 4和2 3 5 6的交集就是2 3 。

观察一下。事实上3是4和6的LCA。2是两个链的顶端较深的那一个。不存在交集的情况就是链底的LCA深度深于当中的一条链的链顶。

多画几个图发现真的是这样。(事实上我仅仅是不会证明罢了。

。。

然后从1到1 << 5枚举取全部边的情况，计算取到n条边时的相交情况，n是计数就加上，是偶数就减去。

CODE：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define MAX 200010#define LEFT (pos << 1)#define RIGHT (pos << 1|1)#define CNT (r - l + 1)using namespace std;pair
         
           ask[MAX];struct SegmentTree{	int sum,c;}tree[MAX << 2];int points,asks;int head[MAX],total;int next[MAX],aim[MAX];int son[MAX],size[MAX],father[MAX],deep[MAX];int pos[MAX],top[MAX],cnt;inline void Add(int x,int y){	next[++total] = head[x];	aim[total] = y;	head[x] = total;}void PreDFS(int x,int last){	father[x] = last;	deep[x] = deep[last] + 1;	size[x] = 1;	for(int i = head[x]; i; i = next[i]) {		if(aim[i] == last)	continue;		PreDFS(aim[i],x);		size[x] += size[aim[i]];		if(size[aim[i]] > size[son[x]])			son[x] = aim[i];	}}void DFS(int x,int _top){	pos[x] = ++cnt;	top[x] = _top;	if(son[x])	DFS(son[x],_top);	for(int i = head[x]; i; i = next[i]) {		if(aim[i] == father[x] || aim[i] == son[x])	continue;		DFS(aim[i],aim[i]);	}}inline void PushDown(int pos,int cnt){	if(tree[pos].c) {		tree[LEFT].c += tree[pos].c;		tree[RIGHT].c += tree[pos].c;		tree[LEFT].sum += tree[pos].c * (cnt - (cnt >> 1));		tree[RIGHT].sum += tree[pos].c * (cnt >> 1);		tree[pos].c = 0;	}}void Modify(int l,int r,int x,int y,int pos,int c){	if(l == x && r == y) {		tree[pos].c += c;		tree[pos].sum += CNT * c;		return ;	}	PushDown(pos,CNT);	int mid = (l + r) >> 1;	if(y <= mid)	Modify(l,mid,x,y,LEFT,c);	else if(x > mid)	Modify(mid + 1,r,x,y,RIGHT,c);	else {		Modify(l,mid,x,mid,LEFT,c);		Modify(mid + 1,r,mid + 1,y,RIGHT,c);	}		tree[pos].sum = tree[LEFT].sum + tree[RIGHT].sum;}int Ask(int l,int r,int x,int y,int pos){	if(l == x && r == y)		return tree[pos].sum;	PushDown(pos,CNT);	int mid = (l + r) >> 1;	if(y <= mid)	return Ask(l,mid,x,y,LEFT);	if(x > mid)		return Ask(mid + 1,r,x,y,RIGHT);	int left = Ask(l,mid,x,mid,LEFT);	int right = Ask(mid + 1,r,mid + 1,y,RIGHT);	return left + right;}inline int Ask(int x,int y){	int re = 0;	while(top[x] != top[y]) {		if(deep[top[x]] < deep[top[y]])			swap(x,y);		re += Ask(1,cnt,pos[top[x]],pos[x],1);		x = father[top[x]];	}	if(deep[x] < deep[y])	swap(x,y);	re += Ask(1,cnt,pos[y],pos[x],1);	return re;}inline int GetLCA(int x,int y){	while(top[x] != top[y]) {		if(deep[top[x]] < deep[top[y]])			swap(x,y);		x = father[top[x]];	}	return deep[x] < deep[y] ? x:y;}inline bool Merge(pair
          
            &a,pair
           
             b){ if(deep[a.first] < deep[a.second]) swap(a.first,a.second); if(deep[b.first] < deep[b.second]) swap(b.first,b.second); int lca = GetLCA(a.first,b.first); if(deep[a.second] > deep[lca] || deep[b.second] > deep[lca]) return false; a.first = lca; a.second = deep[a.second] > deep[b.second] ? a.second:b.second; return true;}inline int Calc(int cnt,int status){ int p = 0; for(int i = 0; i < cnt; ++i) p += (status >> i)&1; p = p&1 ? 1:-1; pair
            
              now(0,0); for(int i = 0; i < cnt; ++i) if((status >> i)&1) { if(!now.first) now = ask[i + 1]; else if(!Merge(now,ask[i + 1])) return 0; } //cout << status << ' ' << now.first << ' ' << now.second << ' ' << Ask(now.first,now.second) << ' ' << p << endl; return p * Ask(now.first,now.second);}inline int MainTask(int cnt){ int re = 0; for(int i = 1; i <= cnt; ++i) scanf("%d%d",&ask[i].first,&ask[i].second); for(int i = 1; i < (1 << cnt); ++i) re += Calc(cnt,i); return re;}int main(){ cin >> points; for(int x,y,i = 1; i < points; ++i) { scanf("%d%d",&x,&y); Add(x,y); } PreDFS(1,0); DFS(1,1); cin >> asks; for(int flag,i = 1; i <= asks; ++i) { scanf("%d",&flag); if(!flag) { int x,y; scanf("%d%d",&x,&y); Modify(1,cnt,pos[x],pos[x] + size[x] - 1,1,y); } else { int cnt; scanf("%d",&cnt); printf("%d\n",MainTask(cnt)&0x7fffffff); } } return 0;}
            
           
          
         
        
       
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。