【題目描述】菊菊是一個(gè)碼農(nóng),他很喜歡碼一些高(e)級(jí)(xin)數(shù)據(jù)結(jié)構(gòu)。有一天,菊菊在打網(wǎng)賽時(shí)遇到了 wfj。wfj 覺(jué)得他很有前途,可以做下一代碼農(nóng)大神。于是乎,wfj 給菊菊出了一道題,來(lái)檢驗(yàn)一下菊菊的代碼能力:這是一個(gè)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)題,你只需在樹(shù)上維護(hù)如下幾個(gè)簡(jiǎn)單操作:type=1:樹(shù)上單點(diǎn)修改,給定 x,v,把 x 的值改為 v。type=2:樹(shù)上子樹(shù)修改,給定 x,v,把 x 子樹(shù)上的所有數(shù)加上 v。type=3:樹(shù)上路徑修改,給定 x,y,v,把 x 到 y 路徑上的所有數(shù)加上 v。type=4:樹(shù)上單點(diǎn)查詢,給定 x,查詢 x 的值。type=5:樹(shù)上子樹(shù)查詢,給定 x,查詢子樹(shù) x 的和。type=6:樹(shù)上路徑查詢,給定 x,y,查詢 x 到 y 路徑上數(shù)的和。wfj 想了很久,覺(jué)得這題太容易了,沒(méi)有任何意義。所以,在上面這些操作完成以后,他還要求菊菊完成另外一些操作:type=7:樹(shù)上子樹(shù)查詢區(qū)間第 k 小,給定 x,k,求 x 子樹(shù)上第 k 小值。type=8:樹(shù)上子樹(shù)查詢比給定數(shù)小的數(shù)的個(gè)數(shù),給定 x,k,求 x 子樹(shù)上比 k 小的數(shù)的個(gè)數(shù)。type=9:樹(shù)上路徑查詢區(qū)間第 k 小,給定 x,y,k(huaji.jpg),求 x 到 y 路徑上的區(qū)間第 k 小。type=10:樹(shù)上路徑查詢比給定數(shù)小的數(shù)的個(gè)數(shù),給定 x,y,k,求 x 到 y 路徑上比 k 小的數(shù)的個(gè)數(shù)。wfj 又想了很久,覺(jué)得這題可以了。然而這時(shí),菊菊對(duì)他說(shuō):“這也太容易了吧!我半小時(shí)就能 AC!”于是 wfj 怒了。他想:這個(gè) sb,我再加一問(wèn),不信他寫(xiě) 得出。于是,wfj加了最后一問(wèn):對(duì)于這棵樹(shù),請(qǐng)求出這棵樹(shù)中<=k 的路徑條數(shù),其中,k 為給定值。菊菊是一個(gè)智商特別高的編程天才,他身上帶了電腦,但他這回做不出來(lái)了,所以他委托你——一位植樹(shù)工人來(lái)完成這個(gè)游戲。你能幫幫他嗎?【輸入數(shù)據(jù)】第一行包括兩個(gè)整數(shù) N,表示這顆樹(shù)的結(jié)點(diǎn)數(shù)。接下來(lái)一行包括 N 個(gè)整數(shù) Ai,表示 N 個(gè)結(jié)點(diǎn)初始權(quán)值。接下來(lái)有 N-1 行,每行兩個(gè)數(shù) x,y,表示 x 和 y 之間有邊相連。接下來(lái)一行包括一個(gè)整數(shù) M1,表示第一問(wèn)的詢問(wèn)數(shù)。接下來(lái) M1 行每行包括一個(gè)數(shù) type,后接幾個(gè)數(shù):type=1:輸入 x,v。type=2:輸入 x,v。type=3:輸入 x,y,v。type=4:輸入 x。type=5:輸入 x。type=6:輸入 x,y。接下來(lái)一行一個(gè)數(shù) M2,表示第二問(wèn)的詢問(wèn)數(shù)。接下來(lái) M2 行:type=7:輸入 x,k。type=8:輸入 x,k。type=9:輸入 x,y,k。type=10:輸入 x,y,k。

最后一行一個(gè)整數(shù) k。以上輸入意義見(jiàn)題中所述?！据敵鰯?shù)據(jù)】對(duì)于每個(gè)查詢操作,每行輸出一個(gè)答案。最后一行為最后一問(wèn)的答案?！据斎霕永?1】500000122324356134432133342546344722835934210 4 5 23【輸出樣例 1】4519515010【輸入樣例 2、3】見(jiàn)下發(fā)樣例文件?！据敵鰳永?2、3】見(jiàn)下發(fā)樣例文件?！緮?shù)據(jù)約定】對(duì)于 30%的數(shù)據(jù),滿足 N<=3000。M1,M2<=3000。對(duì)于 100%的數(shù)據(jù),滿足 N<=100000。M1,M2<=100000。(ps:簡(jiǎn)單送肉板子題,應(yīng)該有人 AC 吧。。)

正解：樹(shù)鏈剖分+線段樹(shù)+主席樹(shù)+點(diǎn)分治。

全部是板子，出了這道題為了訓(xùn)練代碼能力?？紙?chǎng)上無(wú)人寫(xiě)出正解，1人寫(xiě)對(duì)30分暴力。。

//It is made by wfj_2048~#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#define N (100010)#define inf (1<<30)#define lson (x<<1)#define rson (x<<1|1)#define il inline#define RG register#define ll long long#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)using namespace std;struct edge{	ll nt,to;} g[2*N];ll head[N],top[N],fa[N],son[N],size[N],dep[N],dfn[N],pos[N],cur[N],vis[N],dis[N],a[N],W[N],num[N],hsh[N],root1[N],root2[N],lazy[4*N],sum[4*N],sum1[20*N],sum2[20*N],ls1[20*N],rs1[20*N],ls2[20*N],rs2[20*N],n,ssz,sz,sz1,sz2,cnt,tot,root,limit,ans;il ll gi(){	RG ll x=0,q=1;	RG char ch=getchar();	while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();	if (ch=='-') q=-1,ch=getchar();	while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();	return q*x;}il void insert(RG ll from,RG ll to){	g[++sz]=(edge) {head[from],to},head[from]=sz;	return;}il void dfs1(RG ll x,RG ll p){	dep[x]=dep[p]+1,fa[x]=p,size[x]=1;	RG ll v,mx=0;	for (RG ll i=head[x]; i; i=g[i].nt)	{		v=g[i].to;		if (v==p) continue;		dfs1(v,x);		size[x]+=size[v];		if (size[mx]<=size[v]) mx=v;	}	son[x]=mx;	return;}il void dfs2(RG ll x,RG ll p,RG ll a){	top[x]=a,dfn[x]=++cnt,pos[cnt]=x;	if (son[x]) dfs2(son[x],x,a);	RG ll v;	for (RG ll i=head[x]; i; i=g[i].nt)	{		v=g[i].to;		if (v==p || v==son[x]) continue;		dfs2(v,x,v);	}	return;}il void down(RG ll x,RG ll l,RG ll r){	RG ll mid=(l+r)>>1;	sum[lson]+=lazy[x]*(mid-l+1),sum[rson]+=lazy[x]*(r-mid);	lazy[lson]+=lazy[x],lazy[rson]+=lazy[x],lazy[x]=0;	return;}il void build(RG ll x,RG ll l,RG ll r){	if (l==r)	{		sum[x]=a[pos[l]];		return;	}	RG ll mid=(l+r)>>1;	build(lson,l,mid);	build(rson,mid+1,r);	sum[x]=sum[lson]+sum[rson];	return;}il void update(RG ll x,RG ll l,RG ll r,RG ll xl,RG ll xr,RG ll v,RG ll flag){	if (xl<=l && r<=xr)	{		if (flag) sum[x]+=(r-l+1)*v,lazy[x]+=v;		else sum[x]=v;		return;	}	if (lazy[x]) down(x,l,r);	RG ll mid=(l+r)>>1;	if (xr<=mid) update(lson,l,mid,xl,xr,v,flag);	else if (xl>mid) update(rson,mid+1,r,xl,xr,v,flag);	else	{		update(lson,l,mid,xl,mid,v,flag);		update(rson,mid+1,r,mid+1,xr,v,flag);	}	sum[x]=sum[lson]+sum[rson];	return;}il ll query(RG ll x,RG ll l,RG ll r,RG ll xl,RG ll xr){	if (xl<=l && r<=xr) return sum[x];	if (lazy[x]) down(x,l,r);	RG ll mid=(l+r)>>1;	if (xr<=mid) return query(lson,l,mid,xl,xr);	else if (xl>mid) return query(rson,mid+1,r,xl,xr);	else return query(lson,l,mid,xl,mid)+query(rson,mid+1,r,mid+1,xr);}il void change(RG ll u,RG ll v,RG ll w){	while (top[u]!=top[v])	{		if (dep[top[u]]<dep[top[v]]) swap(u,v);		update(1,1,n,dfn[top[u]],dfn[u],w,1);		u=fa[top[u]];	}	if (dep[u]>dep[v]) swap(u,v);	update(1,1,n,dfn[u],dfn[v],w,1);	return;}il ll Query(RG ll u,RG ll v){	RG ll res=0;	while (top[u]!=top[v])	{		if (dep[top[u]]<dep[top[v]]) swap(u,v);		res+=query(1,1,n,dfn[top[u]],dfn[u]);		u=fa[top[u]];	}	if (dep[u]>dep[v]) swap(u,v);	res+=query(1,1,n,dfn[u],dfn[v]);	return res;}il ll lca(RG ll u,RG ll v){	while (top[u]!=top[v])	{		if (dep[top[u]]<dep[top[v]]) swap(u,v);		u=fa[top[u]];	}	return dep[u]>dep[v] ? v : u;}il void kth1build(RG ll x,RG ll &y,RG ll l,RG ll r,RG ll v){	sum1[y=++sz1]=sum1[x]+1,ls1[y]=ls1[x],rs1[y]=rs1[x];	if (l==r) return;	RG ll mid=(l+r)>>1;	if (v<=mid) kth1build(ls1[x],ls1[y],l,mid,v);	else kth1build(rs1[x],rs1[y],mid+1,r,v);	return;}il ll kth1query1(RG ll x,RG ll y,RG ll k){	RG ll l=1,r=tot,mid,tmp;	while (l<r)	{		mid=(l+r)>>1,tmp=sum1[ls1[y]]-sum1[ls1[x]];		if (k<=tmp) r=mid,x=ls1[x],y=ls1[y];		else l=mid+1,k-=tmp,x=rs1[x],y=rs1[y];	}	return hsh[l];}il ll kth1query2(RG ll x,RG ll y,RG ll k){	if (!k) return 0;	RG ll l=1,r=tot,mid,ans=0;	while (l<r)	{		mid=(l+r)>>1;		if (k<=mid) r=mid,x=ls1[x],y=ls1[y];		else		{			ans+=sum1[ls1[y]]-sum1[ls1[x]];			l=mid+1,x=rs1[x],y=rs1[y];		}	}	return ans+sum1[y]-sum1[x];}il void kth2build(RG ll x,RG ll &y,RG ll l,RG ll r,RG ll v){	sum2[y=++sz2]=sum2[x]+1,ls2[y]=ls2[x],rs2[y]=rs2[x];	if (l==r) return;	RG ll mid=(l+r)>>1;	if (v<=mid) kth2build(ls2[x],ls2[y],l,mid,v);	else kth2build(rs2[x],rs2[y],mid+1,r,v);	return;}il ll kth2query1(RG ll u,RG ll v,RG ll k){	RG ll Lca=lca(u,v),l=1,r=tot,mid,tmp;	RG ll a=root2[dfn[u]],b=root2[dfn[v]];	RG ll c=root2[dfn[Lca]],d=root2[dfn[fa[Lca]]];	while (l<r)	{		mid=(l+r)>>1,tmp=sum2[ls2[a]]+sum2[ls2[b]]-sum2[ls2[c]]-sum2[ls2[d]];		if (k<=tmp) r=mid,a=ls2[a],b=ls2[b],c=ls2[c],d=ls2[d];		else k-=tmp,l=mid+1,a=rs2[a],b=rs2[b],c=rs2[c],d=rs2[d];	}	return hsh[l];}il ll kth2query2(RG ll u,RG ll v,RG ll k){	if (!k) return 0;	RG ll Lca=lca(u,v),l=1,r=tot,mid,ans=0;	RG ll a=root2[dfn[u]],b=root2[dfn[v]],c=root2[dfn[Lca]],d=root2[dfn[fa[Lca]]];	while (l<r)	{		mid=(l+r)>>1;		if (k<=mid) r=mid,a=ls2[a],b=ls2[b],c=ls2[c],d=ls2[d];		else		{			ans+=sum2[ls2[a]]+sum2[ls2[b]]-sum2[ls2[c]]-sum2[ls2[d]],l=mid+1;			a=rs2[a],b=rs2[b],c=rs2[c],d=rs2[d];		}	}	return ans+sum2[a]+sum2[b]-sum2[c]-sum2[d];}il void dfs3(RG ll x){	kth2build(root2[dfn[fa[x]]],root2[dfn[x]],1,tot,num[dfn[x]]);	for (RG ll i=head[x]; i; i=g[i].nt)	{		RG ll v=g[i].to;		if (v==fa[x]) continue;		dfs3(v);	}	return;}il void getroot(RG ll x,RG ll p){	size[x]=1,son[x]=0;	for (RG ll i=head[x]; i; i=g[i].nt)	{		RG ll v=g[i].to;		if (vis[v] || v==p) continue;		getroot(v,x);		size[x]+=size[v];		son[x]=max(son[x],size[v]);	}	son[x]=max(son[x],son[0]-size[x]);	if (son[x]<son[root]) root=x;	return;}il void getdis(RG ll x,RG ll p){	cur[++ssz]=dis[x];	for (RG ll i=head[x]; i; i=g[i].nt)	{		RG ll v=g[i].to;		if (vis[v] || v==p) continue;		dis[v]=dis[x]+1;		getdis(v,x);	}	return;}il ll cont(RG ll x,RG ll mit){	RG ll res=0;	dis[x]=mit,ssz=0;	getdis(x,0);	sort(cur+1,cur+ssz+1);	for (RG ll l=1,r=ssz; l<r;)		if (cur[l]+cur[r]<=limit) res+=(r-l++);		else r--;	return res;}il void solve(RG ll x){	vis[x]=1;	ans+=cont(x,0);	for (RG ll i=head[x]; i; i=g[i].nt)	{		RG ll v=g[i].to;		if (vis[v]) continue;		ans-=cont(v,1),root=0,son[0]=size[v];		getroot(v,0),solve(root);	}	return;}il void work(){	n=gi();	RG ll m1,m2,u,v,w,x,k,type;	for (RG ll i=1; i<=n; ++i) a[i]=gi();	for (RG ll i=1; i<n; ++i)	{		u=gi(),v=gi();		insert(u,v),insert(v,u);	}	dfs1(1,0),dfs2(1,0,1);	build(1,1,n);	m1=gi();	for (RG ll i=1; i<=m1; ++i)	{		type=gi();		if (type==1)		{			x=gi(),w=gi();			update(1,1,n,dfn[x],dfn[x],w,0);		}		if (type==2)		{			x=gi(),w=gi();			update(1,1,n,dfn[x],dfn[x]+size[x]-1,w,1);		}		if (type==3)		{			u=gi(),v=gi(),w=gi();			change(u,v,w);		}		if (type==4)		{			x=gi();			PRintf("%lld/n",query(1,1,n,dfn[x],dfn[x]));		}		if (type==5)		{			x=gi();			printf("%lld/n",query(1,1,n,dfn[x],dfn[x]+size[x]-1));		}		if (type==6)		{			u=gi(),v=gi();			printf("%lld/n",Query(u,v));		}	}	for (RG ll i=1; i<=n; ++i) num[i]=W[i]=query(1,1,n,i,i);	sort(num+1,num+n+1);	hsh[tot=1]=num[1];	for (RG ll i=2; i<=n; ++i) if (num[i]>num[i-1]) hsh[++tot]=num[i];	for (RG ll i=1; i<=n; ++i) num[i]=lower_bound(hsh+1,hsh+tot+1,W[i])-hsh;	for (RG ll i=1; i<=n; ++i) kth1build(root1[i-1],root1[i],1,tot,num[i]);	dfs3(1);	m2=gi();	for (RG ll i=1; i<=m2; ++i)	{		type=gi();		if (type==7)		{			x=gi(),k=gi();			printf("%lld/n",kth1query1(root1[dfn[x]-1],root1[dfn[x]+size[x]-1],k));		}		if (type==8)		{			x=gi(),k=gi();			if (k>hsh[tot]) k=tot;			else if (k<hsh[1]) k=0;			else k=upper_bound(hsh+1,hsh+tot+1,k)-hsh-1;			printf("%lld/n",kth1query2(root1[dfn[x]-1],root1[dfn[x]+size[x]-1],k));		}		if (type==9)		{			u=gi(),v=gi(),k=gi();			printf("%lld/n",kth2query1(u,v,k));		}		if (type==10)		{			u=gi(),v=gi(),k=gi();			if (k>hsh[tot]) k=tot;			else if (k<hsh[1]) k=0;			else k=upper_bound(hsh+1,hsh+tot+1,k)-hsh-1;			printf("%lld/n",kth2query2(u,v,k));		}	}	limit=gi();	ans=0,root=0,son[0]=n;	getroot(1,0);	solve(root);	printf("%lld/n",ans);	return;}int main(){	File("structure");	work();	return 0;}