Description

Input

Output

Sample Input

10 5 6
1 2 3 4 5 6 7 8 9 10
9 7
7 10
6 5
7 5
5 8
5 1
2 1
3 2
2 4
2 3 4
2 9 5
1 7 3
4 8 2
5 6 6
2 3
2 5
1 4
3 5
5 1
6 1

Sample Output

0
43
4
27
11
13

Data Constraint

Hint

Solution

题意：

• 给定一棵以 1 为根的树，树上结点上有一些数字。

• 这些数字每过单位 1 时间会走到其所在结点的父亲上，结点 1 上的数字会消失。

• 有若干询问，问某一时间一棵子树中的数字和。

思路：

• 我们考虑一个数字会被一个询问统计到是一种什么情况：

• 设这个数字在 txtx 时间出现在结点 xx 上，然后会被结点 yy 在 tyty 时间统计，

• 那么就会满足不等式：

  ① dep[x]−dep[y]≥ty−txdep[x]−dep[y]≥ty−tx 且 tx≤tytx≤ty ；
  ②xx 必须在 yy 的子树内；

• 其中 dep[i]dep[i] 表示结点 ii 的深度。

• 考虑①：我们移项，就会有 dep[x]+tx≥dep[y]+tydep[x]+tx≥dep[y]+ty，

• 显然左边只会和 xx 有关，右边只会和 yy 有关；

• 考虑②：我们考虑使用 dfsdfs 序，

• 那么②等价于 dfn[x]≥dfn[y]dfn[x]≥dfn[y] 且 dfn[x]<dfn[x]+size[x]dfn[x]<dfn[x]+size[x]，

• 其中 dfn[i]dfn[i] 表示 ii 的 dfsdfs 序，

• Size[i]Size[i] 表示以 ii 为子树的结点个数。

• 综上，我们把题目中的第 xx 数字写成二维平面上的一个带权点，

• 横坐标为 dep[x]+txdep[x]+tx ，纵坐标为 dfn[x]dfn[x]，权值为这个数字。

• 那么询问就相当于是询问一个矩形的点权和。

• 为了支持平面上单点修改，矩形求和。

• 我们有两种方法：

  1 . cdq分治+树状数组

• 我们把修改和询问在一起按时间（题目中的 tt）排序，一共 n+m+qn+m+q 个东西。

• 我们从 [1,n+m+q][1,n+m+q] 开始递归；

• 对于递归一个 [l,r][l,r] 的区间，设 mid=(l+r)/2mid=(l+r)/2

• 我们只考虑 [l,mid][l,mid] 的修改对 [mid+1,r][mid+1,r] 的询问的贡献；

• 这之后，递归到 [l,mid][l,mid] , [mid+1,r][mid+1,r] 中继续处理。

• 现在我们就只用考虑 [l,mid][l,mid] 的修改对 [mid+1,r][mid+1,r] 的询问的贡献；

• 我们可以简单地对 [l,mid][l,mid] 中的修改的横坐标排序，然后把纵坐标插入树状数组中，

• 那么 [mid+1,r][mid+1,r] 中的询问就能通过查询树状数组来实现统计的过程。

  2 . 二维数据结构

• 这个就直接做就好了。

• 只要你会任何二维的数据结构就可以。

• 推荐学习：树状数组套线段树。

• 时间复杂度 O(Nlog2N)O(Nlog2N) 。

Code

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; const int N=1e5+5; struct data {int ty,t,x,w; }a[N*3]; int tot,num; int first[N],nex[N<<1],en[N<<1]; int dep[N],dfn[N],size[N]; int id[N*3]; long long f[N],ans[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline void insert(int x,int y) {nex[++tot]=first[x];first[x]=tot;en[tot]=y; } void dfs(int x,int y) {dfn[x]=++tot;dep[x]=dep[y]+1;size[x]=1;for(int i=first[x];i;i=nex[i])if(en[i]^y){dfs(en[i],x);size[x]+=size[en[i]];} } inline bool cmpt(data x,data y) {return x.t<y.t || x.t==y.t && !x.ty && y.ty; } inline bool cmpx(int x,int y) {return a[x].t>a[y].t; } inline void change(int x,int y) {while(x<N) f[x]=y?f[x]+y:0,x+=x&-x; } inline long long find(int x) {long long sum=0;while(x) sum+=f[x],x-=x&-x;return sum; } void solve(int l,int r) {if(l==r) return;int mid=l+r>>1;int nn=l-1,mm=mid;for(int i=l;i<=mid;i++)if(!a[i].ty) id[++nn]=i;for(int i=mid+1;i<=r;i++)if(a[i].ty) id[++mm]=i;if(nn>=l && mm>mid){sort(id+l,id+1+nn,cmpx);sort(id+mid+1,id+1+mm,cmpx);for(int i=mid+1,j=l;i<=mm;i++){while(j<=nn && a[id[j]].t>=a[id[i]].t){change(dfn[a[id[j]].x],a[id[j]].w);j++;}ans[a[id[i]].w]+=find(dfn[a[id[i]].x]+size[a[id[i]].x]-1)-find(dfn[a[id[i]].x]-1);}for(int i=l;i<=nn;i++) change(dfn[a[id[i]].x],0);}if(nn>=l && nn<mid) solve(l,mid);if(mm>mid && mm<r) solve(mid+1,r); } int main() {freopen("appletree.in","r",stdin);freopen("appletree.out","w",stdout);int n=read(),m=read(),q=read();for(int i=1;i<=n;i++){a[++num].x=i;a[num].t=1;a[num].w=read();}for(int i=1;i<n;i++){int x=read(),y=read();insert(x,y);insert(y,x);}dfs(1,tot=0);for(int i=1;i<=m;i++){a[++num].t=read()+1;a[num].x=read();a[num].w=read();}for(int i=1;i<=q;i++){a[++num].ty=1;a[num].t=read();a[num].x=read();a[num].w=i;}sort(a+1,a+1+num,cmpt);for(int i=1;i<=num;i++) a[i].t+=dep[a[i].x];solve(1,num);for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);return 0; }

总结

以上是生活随笔为你收集整理的JZOJ 5699. 【gdoi2018 day1】涛涛接苹果（appletree）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。