正題

題目鏈接:https://gmoj.net/senior/#main/show/5699

---

題目大意

一棵樹，每個節(jié)點(diǎn)有權(quán)值，每天所有權(quán)值會往它的父節(jié)點(diǎn)滑一位，然后有操作會在某一天的某個節(jié)點(diǎn)加權(quán)值。

然后詢問若干次某個時間一個位置的子樹權(quán)值和。

---

解題思路

因為每次滑一位，所以我們直接把深度帶到時間里，也就是帶入$t+de{p}_x$。

這樣就可以只看時間了，那么對于一個詢問$(t_1,x_1)$，會被修改$(t_2,x_2,w)$影響當(dāng)且僅當(dāng)。$$t_2\le t_1且t_1+de{p}_{x_1}\ge t_2+de{p}_{x_2}$$

然后樹套樹做即可。

時間復(fù)雜度$O((n+q){\log }^{2}n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define lowbit(x) (x&-x) using namespace std; const int N=2e5+10; struct enode{int to,next; }a[N]; struct qnode{int t,x,w; }q[N*2]; int n,m,T,cnt,num,tot,ls[N],rfn[N],ed[N],rt[N],dep[N]; ll ans[N]; struct Seg_Tree{int cnt,ls[N<<6],rs[N<<6];ll val[N<<6];void Change(int &x,int l,int r,int pos,int w){if(!x)x=++cnt;if(l==r){val[x]+=w;return;}int mid=(l+r)>>1;if(pos<=mid)Change(ls[x],l,mid,pos,w);else Change(rs[x],mid+1,r,pos,w);val[x]=val[ls[x]]+val[rs[x]];return;}ll Ask(int x,int L,int R,int l,int r){if(!x)return 0;if(L==l&&R==r)return val[x];int mid=(L+R)>>1;if(r<=mid)return Ask(ls[x],L,mid,l,r);if(l>mid)return Ask(rs[x],mid+1,R,l,r);return Ask(ls[x],L,mid,l,mid)+Ask(rs[x],mid+1,R,mid+1,r);} }Tr; void Change(int x,int pos,int val){x=N-x;while(x<N){Tr.Change(rt[x],1,n,pos,val);x+=lowbit(x);}return; } ll Ask(int x,int l,int r){ll ans=0;x=N-x;while(x){ans+=Tr.Ask(rt[x],1,n,l,r);x-=lowbit(x);}return ans; } void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x,int fa){rfn[x]=++num;dep[x]=dep[fa]+1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;dfs(y,x);}ed[x]=num; } bool cmp(qnode x,qnode y){if(x.t==y.t)return x.w<y.w;return x.t<y.t; } int main() {freopen("appletree.in","r",stdin);freopen("appletree.out","w",stdout);scanf("%d%d%d",&n,&m,&T);for(int i=1;i<=n;i++){int w;scanf("%d",&w);q[++cnt]=(qnode){0,i,w};}for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}dfs(1,1);for(int i=1;i<=m;i++){int t,x,w;scanf("%d%d%d",&t,&x,&w);q[++cnt]=(qnode){t,x,w};}for(int i=1;i<=T;i++){int t,x;scanf("%d%d",&t,&x);q[++cnt]=(qnode){t,x,-i};}sort(q+1,q+1+cnt,cmp);for(int i=1;i<=cnt;i++){if(q[i].w<0)ans[-q[i].w]=Ask(q[i].t+dep[q[i].x]-1,rfn[q[i].x],ed[q[i].x]); else Change(q[i].t+dep[q[i].x],rfn[q[i].x],q[i].w);}for(int i=1;i<=T;i++)printf("%lld\n",ans[i]); }

總結(jié)

以上是生活随笔為你收集整理的jzoj5699-[GDOI2018day1]涛涛接苹果【树套树】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。