HDU4918 经典的树分治的题目。进行点分治。题意：给一颗树，每个点有权值。两种操作：一种是把某个点的权值改为v. 一种是查询距离u不超过d的权值和。树分治结合树状数组去搞。树分治的关键就是每个点最多被logn个点更新到。这样的话，就很容易搞了、

Query on the subtree

Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 320 Accepted Submission(s): 109

Problem Description

bobo has a tree, whose vertices are conveniently labeled by 1,2,…,n. At the very begining, the i-th vertex is assigned with weight wi.There are q operations. Each operations are of the following 2 types: Change the weight of vertex v into x (denoted as “! v x”), Ask the total weight of vertices whose distance are no more than d away from vertex v (denoted as “? v d”). Note that the distance between vertex u and v is the number of edges on the shortest path between them.

Input

The input consists of several tests. For each tests:The first line contains n,q (1≤n,q≤105). The second line contains n integers w1,w2,…,wn (0≤wi≤104). Each of the following (n - 1) lines contain 2 integers ai,bidenoting an edge between vertices ai and bi (1≤ai,bi≤n). Each of the following q lines contain the operations (1≤v≤n,0≤x≤104,0≤d≤n).

Output

For each tests:For each queries, a single number denotes the total weight.

Sample Input

4 3 1 1 1 1 1 2 2 3 3 4 ? 2 1 ! 1 0 ? 2 1 3 3 1 2 3 1 2 1 3 ? 1 0 ? 1 1 ? 1 2

Sample Output

3 2 1 6 6

Author

Xiaoxu Guo (ftiasch)

Source

2014 Multi-University Training Contest 5

/* ***
Author :kuangbin
Created Time :2014/9/25 23:04:05
File Name :E:\2014ACM\专题学习\树分治\HDU4918.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 100010;
const int MAXD = 40;
int cc[MAXNMAXD];
int cc_tail; //记得初始化cc_tail = cc
//0-based BinaryIndexTree
struct BIT{
int c;
int n;
void init(int _n){
n = _n;
c = cc_tail;
cc_tail = cc_tail + n;
memset(c,0,sizeof(int)n);
}
void add(int i,int val){
while(i < n){
c[i] += val;
i += ~i & i+1;
}
}
int sum(int i){
i = min(i,n-1);
int s = 0;
while(i >= 0){
s += c[i];
i -= ~i & i+1;
}
return s;
}
}bits[MAXN<<1];
struct Edge{
int to,next;
}edge[MAXN*2];
int head[MAXN],tot;
void init(){
tot = 0;
memset(head,-1,sizeof(head));
}
inline void addedge(int u,int v){
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
int size[MAXN],vis[MAXN],fa[MAXN],que[MAXN];
int TT;
inline int getroot(int u,int &tot){
int Min = MAXN, root = 0;
int l,r;
que[l = r = 1] = u;
fa[u] = 0;
for(;l <= r;l++)
for(int i = head[que[l]];i != -1;i = edge[i].next){
int v = edge[i].to;
if(v == fa[que[l]] || vis[v] == TT)continue;
que[++r] = v;
fa[v] = que[l];
}
tot = r;
for(l–;l;l–){
int x = que[l], Max = 0;
size[x] = 1;
for(int i = head[x];i != -1;i = edge[i].next){
int v = edge[i].to;
if(v == fa[x] || vis[v] == TT)continue;
Max = max(Max,size[v]);
size[x] += size[v];
}
Max = max(Max,r - size[x]);
if(Max < Min){
Min = Max, root = x;
}
}
return root;
}
struct Node{
int root,subtree,dis;
Node(int _root = 0, int _subtree = 0,int _dis = 0){
root = _root;
subtree = _subtree;
dis = _dis;
}
};
vectorvec[MAXN];
int id[MAXN];
int dist[MAXN];
int val[MAXN];
int cnt;
inline void go(int u,int root,int subtree){
int l,r;
que[l = r = 1] = u;
fa[u] = 0; dist[u] = 1;
for(; l <= r;l++){
u = que[l];
vec[u].push_back(Node(id[root],subtree,dist[u]));
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].to;
if(v == fa[u] || vis[v] == TT)continue;
que[++r] = v;
fa[v] = u;
dist[v] = dist[u] + 1;
}
}
bits[subtree].init(r+1);
for(int i = 1;i <= r;i++){
u = que[i];
bits[id[root]].add(dist[u],val[u]);
bits[subtree].add(dist[u],val[u]);
}
}
void solve(int u){
int tot;
int root = getroot(u,tot);
vis[root] = TT;
id[root] = cnt++;
vec[root].push_back(Node(id[root],-1,0));
bits[id[root]].init(tot);
bits[id[root]].add(0,val[root]);
for(int i = head[root];i != -1;i = edge[i].next){
int v = edge[i].to;
if(vis[v] == TT)continue;
go(v,root,cnt);
cnt++;
}
for(int i = head[root];i != -1;i = edge[i].next){
int v = edge[i].to;
if(vis[v] == TT)continue;
solve(v);
}
}
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n,m;
memset(vis,0,sizeof(vis));
TT = 0;
while(scanf(“%d%d”,&n,&m) == 2){
init();
TT++;
cc_tail = cc;
cnt = 0;
for(int i = 1;i <= n;i++)vec[i].clear();
for(int i = 1;i <= n;i++)scanf(“%d”,&val[i]);
int u,v;
for(int i = 1;i < n;i++){
scanf(“%d%d”,&u,&v);
addedge(u,v);
addedge(v,u);
}
solve(1);
char op[10];
int d;
while(m–){
scanf(“%s%d%d”,op,&u,&d);
if(op[0] == ‘!’){
int dv = d - val[u];
int sz = vec[u].size();
for(int i = 0;i < sz;i++){
Node tmp = vec[u][i];
bits[tmp.root].add(tmp.dis,dv);
if(tmp.subtree != -1)
bits[tmp.subtree].add(tmp.dis,dv);
}
val[u] += dv;
}
else {
int ans = 0;
int sz = vec[u].size();
for(int i = 0;i < sz;i++){
Node tmp = vec[u][i];
ans += bits[tmp.root].sum(d-tmp.dis);
if(tmp.subtree != -1)
ans -= bits[tmp.subtree].sum(d-tmp.dis);
}
printf(“%d\n”,ans);
}
}
}
return 0;
}