题目描述

方方方种下了三棵树,两年后,第二棵树长出了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 inline
il int read(){
bool f=true;Ri x=;char ch;while(!isdigit(ch=gc))if(ch=='-')f=false;while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';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[];
int last[],dep[],val[],f[][],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[][],rf[][],bfn[],_bfn;
// i的fib_i层的左&右
void dfs(int x,int fa=){
dep[x]=dep[fa]+;
f[x][]=f[x][]=fa;
for(int i=;i<=;i++)f[x][i]=f[f[x][i-]][i-];
for(int i=last[x];i;i=e[i].next){
if(e[i].to!=fa){
dfs(e[i].to,x);
}
}
}
bool vis[];
void bfs(int s){
memset(vis,,sizeof(vis));
queue<int>q;
q.push(s);vis[s]=true;bfn[]=++_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();
bfs();
memset(lf,,sizeof(lf));
for(int i=;i<=n;i++){
for(int j=;j<=;j++){
int anc=f[i][j];
if(!anc)break;
gmin(lf[anc][j],bfn[i]);
gmax(rf[anc][j],bfn[i]);
}
}
for(int i=;i<=n;i++)
lf[i][]=rf[i][]=bfn[i];
}
namespace bit{
ll a1[],a2[];
ll qzh(int r){
ll s1=,s2=;
for(int i=r;i>=;i-=i&-i) s1+=a1[i], s2+=a2[i];
return (r+)*s1-s2;
}
ll sum(int l,int r){
return qzh(r)-qzh(l-);
}
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+,-a);}
}
void _chg(int x,int y){
for(int i=;i<=;i++){
if(!rf[x][i])break;
bit::edt(lf[x][i],rf[x][i],y);
}
}
ll _qry(int x){
sum=;
for(int i=;i<=;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=;i<n;i++){
int a,b;
a=gi;b=gi;
link(a,b);
}
yuchuli();
while(m--){
int op,x,y;
op=gi;
if(op==){
x=gi;
printf("%I64d\n",_qry(x));
}
if(op==){
x=gi;y=gi;
_chg(x,y);
//puts("");
}
}
}

最新文章

  1. TCP/IP四层模型和OSI七层模型
  2. 面试题整理:SQL(一)
  3. php课程---练习连接数据库及增删改
  4. R&amp;&amp;rstudio
  5. 图片模糊度判断程序(C++、opencv)
  6. 8.1.C++ AMP简介
  7. 2014年度辛星html教程夏季版第四节
  8. (转载)为啥我们要学习Linux
  9. webservice 发布到外网的时候
  10. BeanUtils的日期问题
  11. Inno Setup GIF 显示插件 GIFCtrl (V2.1 版本)
  12. 移动端h5摇一摇事件
  13. mysql shutdown and kill
  14. HashMap的源码分析(一)
  15. UI自动化测试(四)AutoIT工具使用和robot对象模拟键盘按键操作
  16. HDFS的java api操作
  17. JDK1.8源码(二)——java.util.LinkedList
  18. [再寄小读者之数学篇](2014-06-27 向量公式: The Hall term)
  19. 编写程序,使用while循环将50到100的整数相加
  20. 漫画揭秘Hadoop MapReduce | 轻松理解大数据

热门文章

  1. PHPExcel导出导入excel、csv等格式数据
  2. appcan weixin 开发
  3. USB总线介绍
  4. Java当中的I/O的字符流
  5. [Letcode] 1. Two Sum
  6. oracle expdp impdp
  7. Split字符串分割函数
  8. android开发中系统自带语音模块的使用
  9. Swift global function(count indexOfObject contains...)
  10. shell 函数