首页 > 代码库 > HDU 3966 dfs序+LCA+树状数组
HDU 3966 dfs序+LCA+树状数组
题目意思很明白：
给你一棵有n个节点的树，对树有下列操作：
I c1 c2 k 意思是把从c1节点到c2节点路径上的点权值加上k
D c1 c2 k 意思是把从c1节点到c2节点路径上的点权值减去k
Q a 查询节点a的权值
数据大小 节点个数 n[1,50000], 操作次数 op[0,30000];
不会树链剖分 故只有想其他的方法。
这道题有点类似今年上海网络赛的1003 ，不过那题我没做；
算法思路：
以节点1 为根，求出节点i 的 dfs序列 tim[i][2];
其中tim[i][0]存的是进入节点i的时间 ，tim[i][1]存的是离开节点i的时间
看操作： I a b k， 节点a到b的路径上所有点+k；最朴素的算法首先找到他们的最近公共祖先（LCA）（我用RMQ）写的；然后在路径上的每一个节点都+k；
假设树根是1
从a到树根的每一个节点x都满足tim[x][0]<=tim[a][0]<=tim[x][1];如此 如果引入一个数列nt，如果nt（tim[a][0]）+=k,那么 nt数列从tim[x][0]到tim[x][1]项的和就加了k，这就相当于把从a到根节点的每一个节点的权值加上了k；
如果节点x不在a到根的路径上呢？那么只有可能是tim[x][0]>tim[a][0] or tim[x][1]<tim[a][0] 故上面的这种做法对其他的点没有影响
根据这种思路 ，那解法就相对简单了：
加上差分数列的思想
a b的LCA是t，把 a b节点都加上k，然后把t的父节点-2；当然 t节点是加了两遍的 所以需要减去一遍 也就是把t节点-1，父节点当然也要+1了
如果有了dfs序，就可以很清晰的看出来 如果一个节点x在这条路径上 那么tim[x][0]<=one of (tim[a][0],tim[b][0])<=tim[x][1];
附上代码渣渣：
1 // hdu 3966 2 #include<iostream> 3 #include<stdio.h> 4 #include<string.h> 5 #include <string> 6 #include <cmath> 7 #include <algorithm> 8 #include <map> 9 #include <set> 10 #include <queue> 11 #include <stack> 12 #include<stdlib.h> 13 #include <vector> 14 using namespace std; 15 16 #define ll __int64 17 #define CL(a,b) memset(a,b,sizeof(a)) 18 #define MAX_NODE 50010 19 20 int n,m,q; 21 22 int log_2(int x) 23 { 24 return (int)(log((double)x)/log(2.0)); 25 } 26 27 int tim[MAX_NODE][2],ti; 28 int rmq[MAX_NODE*2][30],cq,fv[MAX_NODE]; 29 int pre[MAX_NODE]; 30 int value[50010]; 31 32 typedef struct myedge 33 { 34 int v,next; 35 }E; 36 37 E edge[100010]; 38 int head[50010],ce; 39 40 void inithead() 41 { 42 CL(head,-1); 43 ce=0; 44 } 45 void addedge(int s,int e) 46 { 47 edge[ce].v=e;edge[ce].next=head[s];head[s]=ce++; 48 edge[ce].v=s;edge[ce].next=head[e];head[e]=ce++; 49 } 50 51 void initrmq() 52 { 53 int i,j; 54 for(j=1;(1<<j)<=cq;j++) 55 { 56 for(i=1;i+(1<<j)-1<=cq;i++) 57 { 58 rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]); 59 } 60 } 61 } 62 int quermq(int s,int e) 63 { 64 int i=log_2(e-s+1); 65 return min(rmq[s][i],rmq[e-(1<<i)+1][i]); 66 } 67 68 ll nt[50010]; 69 70 int lowbit(int i) 71 { 72 return i&(-i); 73 } 74 75 void modify(int i,ll v) 76 { 77 if(i==0)return ; 78 for(i;i<=n;i+=lowbit(i)) 79 { 80 nt[i]+=v; 81 } 82 } 83 84 ll sum(int i) 85 { 86 ll rem=0; 87 for(i;i>0;i-=lowbit(i)) 88 rem+=nt[i]; 89 return rem; 90 } 91 92 int dfs(int i,int pr) 93 { 94 ti++; 95 tim[i][0]=ti; 96 // cout<<i<<" tim "<<ti<<endl; 97 rmq[++cq][0]=tim[i][0]; 98 fv[i]=cq; 99 pre[ti]=pr;100 int p=head[i];101 while(p!=-1)102 {103 int v=edge[p].v;104 if(tim[v][0]==0)105 {106 dfs(v,tim[i][0]);107 rmq[++cq][0]=tim[i][0];108 }109 p=edge[p].next;110 }111 tim[i][1]=ti;112 return 0;113 }114 115 void inc(int s,int e,int k)116 {117 int rs=fv[s];118 int re=fv[e];119 int rt=quermq(min(rs,re),max(rs,re));120 re=tim[e][0];121 rs=tim[s][0];122 // cout<<rs<<‘ ‘<<re<<‘ ‘<<rt<<‘ ‘<<pre[rt]<<endl;123 if(s==e)124 {125 value[s]+=k;126 return ;127 }128 modify(rs,k);129 modify(re,k);130 modify(rt,-k);131 modify(pre[rt],-k);132 }133 134 void dec(int s,int e,int k)135 {136 k=-k;137 int rs=fv[s];138 int re=fv[e];139 int rt=quermq(min(rs,re),max(rs,re));140 re=tim[e][0];141 rs=tim[s][0];142 if(s==e)143 {144 value[s]+=k;145 return ;146 }147 modify(rs,k);148 modify(re,k);149 modify(rt,-k);150 modify(pre[rt],-k);151 }152 153 ll que(int k)154 {155 int rl=tim[k][0];156 int rr=tim[k][1];157 // cout<<rl<<‘ ‘<<rr<<endl;158 return (ll)value[k]+sum(rr)-sum(rl-1);159 }160 161 char op[3];162 163 164 int main()165 {166 while(scanf("%d %d %d",&n,&m,&q)!=EOF)167 {168 CL(nt,0);169 CL(rmq,0);cq=0;170 CL(fv,0);171 CL(pre,0);172 CL(tim,0);ti=0;173 inithead();174 int i,j,k;175 int a,b,c;176 for(i=1;i<=n;i++)177 {178 scanf("%d",value+i);179 }180 for(i=1;i<n;i++)181 {182 scanf("%d %d",&a,&b);183 addedge(a,b);184 }185 dfs(1,0);186 /*187 for(i=1;i<=cq;i++)188 {189 printf("%d ",rmq[i][0]);190 }cout<<endl;191 */192 initrmq();193 for(i=0;i<q;i++)194 {195 scanf("%s",op);196 if(op[0]==‘I‘)197 {198 scanf("%d %d %d",&a,&b,&c);199 inc(a,b,c);200 }201 else if(op[0]==‘D‘)202 {203 scanf("%d %d %d",&a,&b,&c);204 dec(a,b,c);205 }206 else if(op[0]==‘Q‘)207 {208 scanf("%d",&a);209 printf("%I64d\n",que(a));210 }211 }212 213 }214 215 return 0;216 }
HDU 3966 dfs序+LCA+树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。