首页 > 代码库 > [51nod1462]树据结构
[51nod1462]树据结构
题面：
给一颗以1为根的树。
每个点有两个权值：vi, ti,一开始全部是零。
Q次操作：
读入o, u, d
o = 1 对u到根上所有点的vi += d
o = 2 对u到根上所有点的ti += vi * d
最后,输出每个点的ti值(n, Q <= 100000)
有50%的数据N,Q <= 10000
每个点有两个权值：vi, ti,一开始全部是零。
Q次操作：
读入o, u, d
o = 1 对u到根上所有点的vi += d
o = 2 对u到根上所有点的ti += vi * d
最后,输出每个点的ti值(n, Q <= 100000)
有50%的数据N,Q <= 10000
注：所有数64位整数不会爆。
一开始以为是链剖板子题，结果发现两个标记没法共存（就是说要更新某个标记的话另一个标记得传下去）
由swm大爷的教导可得T_T，可以搞个3*3的矩阵当标记...
1,0,0
0,1,0
v,t,1
操作1的话就是乘上
1,0,0
0,1,0
d,0,1
操作2的话就是乘上
1,d,0
0,1,0
0,0,1
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define ll long long 7 #define ui unsigned int 8 #define ull unsigned long long 9 const int maxn=100023,mxnode=maxn<<1;10 struct zs{int too,pre;}e[maxn];int tot,last[maxn];11 struct mat{ll mp[3][3];}tag[mxnode],nul={1,0,0,0,1,0,0,0,1};12 int lc[mxnode],rc[mxnode],tt;13 int dfn[maxn],tim,fa[maxn],bel[maxn],sz[maxn];14 int i,j,k,n,m;15 int L,R;mat TAG;16 ll an[maxn];17 18 int ra,fh;char rx;19 inline int read(){20 rx=getchar(),ra=0,fh=1;21 while((rx<‘0‘||rx>‘9‘)&&rx!=‘-‘)rx=getchar();22 if(rx==‘-‘)fh=-1,rx=getchar();23 while(rx>=‘0‘&&rx<=‘9‘)ra*=10,ra+=rx-48,rx=getchar();return ra*fh;24 }25 26 mat operator *(mat a,mat b){27 mat c;28 int i,j,k;29 for(i=0;i<3;i++)for(j=0;j<3;j++)for(k=c.mp[i][j]=0;k<3;k++)30 c.mp[i][j]+=a.mp[i][k]*b.mp[k][j];31 return c;32 }33 34 inline void pushdown(int x){35 if(!tag[x].mp[0][1]&&!tag[x].mp[2][0])return;36 int l=lc[x],r=rc[x];37 tag[l]=tag[l]*tag[x],tag[r]=tag[r]*tag[x],38 tag[x]=nul;39 }40 void insert(int x,int a,int b){41 if(L<=a&&R>=b){tag[x]=tag[x]*TAG;return;}42 pushdown(x);43 int mid=a+b>>1;44 if(L<=mid)insert(lc[x],a,mid);45 if(R>mid)insert(rc[x],mid+1,b);46 }47 void dfss(int x,int a,int b){48 if(a==b){an[a]=tag[x].mp[2][1];return;}49 pushdown(x);50 int mid=a+b>>1;51 dfss(lc[x],a,mid),dfss(rc[x],mid+1,b);52 }53 void build(int a,int b){54 int x=++tt;tag[x]=nul;55 if(a==b)return;56 int mid=a+b>>1;57 lc[x]=tt+1,build(a,mid),rc[x]=tt+1,build(mid+1,b);58 }59 60 61 void dfs(int x){62 sz[x]=1;63 for(int i=last[x];i;i=e[i].pre)64 fa[e[i].too]=x,dfs(e[i].too),sz[x]+=sz[e[i].too];65 }66 void dfs2(int x,int chain){67 int i,mx=0;68 bel[x]=chain,dfn[x]=++tim;69 for(i=last[x];i;i=e[i].pre)if(sz[e[i].too]>sz[mx])mx=e[i].too;70 if(!mx)return;71 dfs2(mx,chain);72 for(i=last[x];i;i=e[i].pre)if(e[i].too!=mx)dfs2(e[i].too,e[i].too);73 }74 void run(int x){75 while(bel[x]!=bel[1])76 L=dfn[bel[x]],R=dfn[x],insert(1,1,n),77 x=fa[bel[x]];78 L=dfn[bel[1]],R=dfn[x],insert(1,1,n);79 }80 81 inline void ins(int a,int b){82 e[++tot].too=b,e[tot].pre=last[a],last[a]=tot;83 }84 int main(){85 n=read();86 for(i=2;i<=n;i++)ins(read(),i);87 dfs(1),dfs2(1,1);88 build(1,n);89 int id,x,d;90 for(m=read();m;m--){91 id=read(),x=read(),d=read();TAG=nul;92 if(id==1)TAG.mp[2][0]=d;else TAG.mp[0][1]=d;93 run(x);94 }95 dfss(1,1,n);96 for(i=1;i<=n;i++)printf("%lld\n",an[dfn[i]]);97 }
还是第一次见这种题。。
[51nod1462]树据结构
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。