就是把树上的路径拆成几段,然后大多按照线段树的解法解就可以了
讲解
http://blog.sina.com.cn/s/blog_7a1746820100wp67.html
模板
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 using namespace std; 12 #define N 50006 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 /* 18 fa[u] u的父亲节点 19 son[u] u的儿子节点 20 dep[u] u的深度 21 top[u] u所在链的深度最小的点 22 siz[u] 以u为根的子树上的节点总数 23 po[u] u在dfs时的时间戳 24 */ 25 struct node 26 { 27 int u,v,next; 28 } ed[N<<1]; 29 int head[N],t; 30 int a[N]; 31 32 void add(int u,int v) 33 { 34 ed[t].u = u,ed[t].v = v; 35 ed[t].next = head[u]; 36 head[u] = t++; 37 } 38 int siz[N],fa[N],son[N],dep[N],top[N],seg[N],po[N]; 39 int tp; 40 void init() 41 { 42 t = 0;tp=0; 43 memset(head,-1,sizeof(head)); 44 memset(son,-1,sizeof(son)); 45 } 46 void dfs1(int u,int pre,int d) 47 { 48 dep[u] = d,fa[u] = pre,siz[u] = 1,son[u] = -1; 49 for(int i = head[u] ; i!=-1 ; i = ed[i].next) 50 { 51 int v = ed[i].v; 52 if(v!=pre) 53 { 54 dfs1(v,u,d+1); 55 if(son[u]==-1||siz[son[u]] >1; 85 build(l,m,w<<1); 86 build(m+1,r,w<<1|1); 87 } 88 void down(int w,int m) 89 { 90 if(s[w]) 91 { 92 s[w<<1]+=s[w]; 93 s[w<<1|1]+=s[w]; 94 s[w] = 0; 95 } 96 } 97 void update(int a,int b,int va,int l,int r,int w) 98 { 99 if(a<=l&&b>=r)100 {101 s[w]+=va;102 return ;103 }104 down(w,r-l+1);105 int m = (l+r)>>1;106 if(a<=m) update(a,b,va,l,m,w<<1);107 if(b>m) update(a,b,va,m+1,r,w<<1|1);108 }109 int query(int p,int l,int r,int w)110 {111 if(l==r)112 {113 return s[w];114 }115 down(w,r-l+1);116 int m = (l+r)>>1;117 if(p<=m) return query(p,l,m,w<<1);118 else return query(p,m+1,r,w<<1|1);119 }120 void solve(int l,int r,int val)121 {122 while(top[l]!=top[r])123 {124 if(dep[top[l]] dep[r]) swap(l,r);129 //对于结点值的操作130 update(po[l],po[r],val,1,n,1);131 /* 对于边权的话,需要减掉lca(l,r) 所以对seg[l]+1操作即可132 if(l!=r)133 update(po[l]+1,po[r],val,1,n,1);134 */135 }136 int main()137 {138 int i,m,Q;139 char str[20];140 while(scanf("%d%d%d",&n,&m,&Q)!=EOF)141 {142 init();143 for(i = 1; i <= n ;i++)144 scanf("%d",&a[i]);145 for(i = 1; i < n; i++)146 {147 int u,v;148 scanf("%d%d",&u,&v);149 add(u,v);150 add(v,u);151 }152 dfs1(1,-1,1);153 154 dfs2(1,-1,1);155 build(1,n,1);156 while(Q--)157 {158 int x,y,z;159 scanf("%s",str);160 161 if(str[0]=='I')162 {163 scanf("%d%d%d",&x,&y,&z);164 solve(x,y,z);165 }166 else if(str[0]=='D')167 {168 scanf("%d%d%d",&x,&y,&z);169 solve(x,y,-z);170 }171 else172 {173 scanf("%d",&x);174 printf("%d\n",query(po[x],1,n,1));175 }176 }177 }178 return 0;179 }