此博客停更

题面见http://www.lydsy.com/JudgeOnline/problem.php?id=3589

本来是被题目名字吸引点进去，然而尼玛不是lct= =

先讲讲2个log的写法吧：

树链求和+子树修改，裸的dfs序树剖，其实还有个log是容斥的2^5次的枚举

然后讲我的1个log的写法：

考虑修改某个点u的子树+k，对于v在u的子树里到根的的路径和的贡献是(dep[v]-dep[u]+1)*k，然后就可以用树状数组/线段树来维护了，复杂度降到一个log，就rank3了= =|||，前排膜叶队

/**************************************************************
    Problem: 3589
    User: qiancl
    Language: C++
    Result: Accepted
    Time:2488 ms
    Memory:16128 kb
****************************************************************/
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 200010
#define uint unsigned int
uint n,m,last[N],sz[N],dep[N],fa[N],son[N],id[N],top[N],cnt,now,rk[N],tr[N],k[N],b[N];
pair<uint,uint>a[6];
struct edge{uint to,next;}e[N<<1];
void dfs(uint x,uint d){
	sz[x]=1,dep[x]=d;
	for(uint y,i=last[x];i;i=e[i].next)
		if((y=e[i].to)!=fa[x]){
			fa[y]=x,dfs(y,d+1);
			if(sz[y]>sz[son[x]])son[x]=y;
			sz[x]+=sz[y];
		}
}
void dfs2(uint x,uint d){
	id[x]=++now,top[x]=d,rk[id[x]]=x;
	if(son[x])dfs2(son[x],d);
	for(uint y,i=last[x];i;i=e[i].next)
		if((y=e[i].to)!=fa[x]&&y!=son[x])dfs2(y,y);
	tr[x]=now;
}
#define nc() getchar()
inline uint read(){
	uint x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
inline void insert(uint u,uint v){
	e[++cnt]=(edge){v,last[u]},last[u]=cnt;
	e[++cnt]=(edge){u,last[v]},last[v]=cnt;
}
inline uint Lca(uint l,uint r){
	while(top[l]!=top[r]){
		if(dep[top[l]]<dep[top[r]])swap(l,r);
		l=fa[top[l]];
	}
	return dep[r]<dep[l]?r:l;
}
inline void b_add(uint x,uint d){for(;x<=n;b[x]+=d,x+=x&-x);}
inline void k_add(uint x,uint d){for(;x<=n;k[x]+=d,x+=x&-x);}
inline int b_ask(uint x){uint ans=0;for(;x;ans+=b[x],x-=x&-x);return ans;}
inline int k_ask(uint x){uint ans=0;for(;x;ans+=k[x],x-=x&-x);return ans;}
#define fr first
#define sc second
inline bool check(pair<uint,uint>&a,pair<uint,uint>b){
	uint lca=Lca(a.fr,b.fr);
	if(dep[a.sc]>dep[lca]||dep[b.sc]>dep[lca])return 0;
	a.fr=lca,a.sc=dep[a.sc]>dep[b.sc]?a.sc:b.sc;
	return 1;
}
inline uint clac(uint o,uint x){
	uint p=0;for(uint i=0;i<o;++i)p+=(x>>i)&1;
	p=p&1?1:-1;pair<uint,uint>now(0,0);
	for(uint i=0;i<o;++i)if((x>>i)&1){
		if(!now.fr)now=a[i+1];
		else if(!check(now,a[i+1]))return 0;
	}
	return p*((dep[now.fr]*k_ask(id[now.fr])+b_ask(id[now.fr]))-(dep[fa[now.sc]]*k_ask(id[fa[now.sc]])+b_ask(id[fa[now.sc]])));
}
int main(){
	n=read();
	for(uint i=1;i<n;insert(read(),read()),++i);
	dfs(1,0),dfs2(1,1);
	m=read();
	while(m--){
		uint c=read(),x,y;
		if(c==0)x=read(),y=read(),k_add(id[x],y),k_add(tr[x]+1,-y),b_add(id[x],(1-dep[x])*y),b_add(tr[x]+1,-(1-dep[x])*y);
		else{
			uint o=read(),ans=0;
			for(uint i=1;i<=o;++i){
				a[i].first=read(),a[i].second=read();
				if(dep[a[i].fr]<dep[a[i].sc])swap(a[i].fr,a[i].sc);
			}
			for(uint i=1,l=(1<<o);i<l;++i)ans+=clac(o,i);
			printf("%d\n",ans&0x7fffffff);
		}
	}
}

loading...