题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4858
题解：
下面说一个插入查询时间复杂度为sqrt(m)的算法：
对每个点定义两个值：val，sum，val记录自己的特征值，sum记录周边所有点特征值的和。
现在我们把所有的节点分成两类，重点(度数>=sqrt(m))，轻点(度数sqrt(m))。
插入：
轻点更新自己的val，同时更新所有的邻点的sum值
重点更新自己的val,同时只更新相邻重点的sum值（所以重点不需要连边到轻点）
查询：
轻点：暴力周边的所有邻点的val值。
重点：直接输出自己的sum值。
性质：
与重点相邻的重点不超过sqrt(m)个。
与轻点相邻的所有点不超过sqrt(m)个。
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<utility>
#include<cmath>
using namespace std; typedef long long LL;
const int maxn=1e5+; vector<int> G[maxn];
pair<int,int> E[maxn]; LL val[maxn],sum[maxn];
int cnt[maxn];
int n,m,q; void init(){
memset(val,,sizeof(val));
memset(sum,,sizeof(sum));
memset(cnt,,sizeof(cnt));
memset(E,,sizeof(E));
for(int i=;i<=n;i++) G[i].clear();
} int main(){
int tc;
scanf("%d",&tc);
while(tc--){
scanf("%d%d",&n,&m);
init();
for(int i=;i<m;i++){
int u,v;
scanf("%d%d",&E[i].first,&E[i].second);
cnt[E[i].first]++,cnt[E[i].second]++;
}
for(int i=;i<m;i++){
int u=E[i].first,v=E[i].second;
if(cnt[u]>cnt[v]) swap(u,v);
if(cnt[u]<sqrt(m+0.5)){
G[u].push_back(v);
if(cnt[v]<sqrt(m+0.5)) G[v].push_back(u);
}
else{
G[u].push_back(v);
G[v].push_back(u);
}
}
scanf("%d",&q);
while(q--){
int cmd; scanf("%d",&cmd);
if(cmd==){
int id,v;
scanf("%d%d",&id,&v);
val[id]+=v;
for(int i=;i<G[id].size();i++){
sum[G[id][i]]+=v;
}
}else{
int id;
scanf("%d",&id);
if(cnt[id]>=sqrt(m+0.5)) printf("%lld\n",sum[id]);
else{
LL res=;
for(int i=;i<G[id].size();i++){
res+=val[G[id][i]];
}
printf("%lld\n",res);
}
}
}
}
return ;
}