首页 > 代码库 > OrzFAng 233–树 解题报告
OrzFAng 233–树 解题报告
题目描述
方方方种下了三棵树，两年后，第二棵树长出了n个节点，其中1号节点是根节点。
给定一个n个点的树
支持两种操作
方方方进行m次操作，每个操作为：
（1）给出两个数i，x，将第i个节点的子树中，与i距离为斐波那契数的节点权值+x（包括i本身）。
（2）给出一个数i，求出第i个节点的子树中，与i距离为斐波那契数的节点的权值和（包括i本身）。
题解
斐波那契数列
首先这个会被操作的只有大概25层的节点。
这样深度相同的区间在bfs序上是连续的区间，那么只要求出这样的左右端点是哪些，后面的就可以建个线段树|树状数组维护
原来我觉得这样的区间很难求。其实只要类似倍增的做法表示i的
次祖先。就可以直接求了。
bfs序上的区间修改/查询 还可以用bit
这类的玩意http://www.cnblogs.com/zzqsblog/p/5692627.html
#include<map>#include<stack>#include<queue>#include<cstdio>#include<string>#include<vector>#include<cstring>#include<complex>#include<iostream>#include<assert.h>#include<algorithm>using namespace std;#define inf 1001001001#define infll 1001001001001001001LL#define ll long long#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl#define gmax(a,b) (a)=max((a),(b))#define gmin(a,b) (a)=min((a),(b))#define Ri register int#define gc getchar()#define il inlineil int read(){ bool f=true;Ri x=0;char ch;while(!isdigit(ch=gc))if(ch==‘-‘)f=false;while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-‘0‘;ch=gc;}return f?x:-x;}#define gi read()#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);struct edge{ int to,next;}e[501234];int last[123456],dep[123456],val[123456],f[123456][34],cnt,n,m;ll sum;il void link(int a,int b){ e[++cnt]=(edge){b,last[a]};last[a]=cnt; e[++cnt]=(edge){a,last[b]};last[b]=cnt;}int lf[123456][34],rf[123456][34],bfn[123456],_bfn;// i的fib_i层的左&右 void dfs(int x,int fa=0){ dep[x]=dep[fa]+1; f[x][1]=f[x][2]=fa; for(int i=3;i<=30;i++)f[x][i]=f[f[x][i-2]][i-1]; for(int i=last[x];i;i=e[i].next){ if(e[i].to!=fa){ dfs(e[i].to,x); } } }bool vis[123456];void bfs(int s){ memset(vis,0,sizeof(vis)); queue<int>q; q.push(s);vis[s]=true;bfn[1]=++_bfn; while(!q.empty()){ int c=q.front();q.pop(); for(int i=last[c];i;i=e[i].next){ if(!vis[e[i].to]){ q.push(e[i].to); vis[e[i].to]=true; bfn[e[i].to]=++_bfn; } } } }void yuchuli(){ dfs(1); bfs(1); memset(lf,127,sizeof(lf)); for(int i=1;i<=n;i++){ for(int j=1;j<=30;j++){ int anc=f[i][j]; if(!anc)break; gmin(lf[anc][j],bfn[i]); gmax(rf[anc][j],bfn[i]); } } for(int i=1;i<=n;i++) lf[i][1]=rf[i][1]=bfn[i];}namespace bit{ ll a1[234567],a2[234567]; ll qzh(int r){ ll s1=0,s2=0; for(int i=r;i>=1;i-=i&-i) s1+=a1[i], s2+=a2[i]; return (r+1)*s1-s2; } ll sum(int l,int r){ return qzh(r)-qzh(l-1); } void edt(ll a,ll s1){ ll s2=a*s1; for(;a<=n;a+=a&-a) a1[a]+=s1, a2[a]+=s2; } void edt(int l,int r,ll a) {edt(l,a); edt(r+1,-a);}}void _chg(int x,int y){ for(int i=1;i<=30;i++){ if(!rf[x][i])break; bit::edt(lf[x][i],rf[x][i],y); }}ll _qry(int x){ sum=0; for(int i=1;i<=30;i++){ if(!rf[x][i])break; sum=sum+bit::sum(lf[x][i],rf[x][i]); } return sum;} int main(){ //FO(tree2); n=gi;m=gi; for(int i=1;i<n;i++){ int a,b; a=gi;b=gi; link(a,b); } yuchuli(); while(m--){ int op,x,y; op=gi; if(op==2){ x=gi; printf("%I64d\n",_qry(x)); } if(op==1){ x=gi;y=gi; _chg(x,y); //puts(""); } }}
OrzFAng 233–树 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。