题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4858
题意：中文题面
思路：来自此博客
对每个点定义两个值：val，sum，val记录自己的特征值，sum记录周边所有点特征值的和。
现在我们把所有的节点分成两类，重点(度数>=sqrt(m))，轻点(度数sqrt(m))。
插入：
轻点更新自己的val，同时更新所有的邻点的sum值
重点更新自己的val,同时只更新相邻重点的sum值（所以重点不需要连边到轻点）
查询：
轻点：暴力周边的所有邻点的val值。
重点：直接输出自己的sum值。
性质：
与重点相邻的重点不超过sqrt(m)个。
与轻点相邻的所有点不超过sqrt(m)个。
#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<queue>
#include<math.h>
#include<time.h>
#include<vector>
#include<iostream>
using namespace std;
typedef long long int LL;
const int MAXN = + ;
struct Edges{
int u, v; Edges(int u = , int v = ) :u(u), v(v){};
};
vector<Edges>edge;
vector<int>G[MAXN];
int val[MAXN],du[MAXN];
LL sum[MAXN];
int main(){
//#ifdef kirito
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
//#endif
// int start = clock();
int t, n, m, q;
scanf("%d", &t);
while (t--){
scanf("%d%d", &n, &m); edge.clear(); int block = (int)sqrt(m + 0.5);
for (int i = ; i <= n; i++){
G[i].clear(); val[i] = ; du[i] = ; sum[i] = ;
}
for (int i = ; i <= m; i++){
int u, v; scanf("%d%d", &u, &v);
edge.push_back(Edges(u, v));
du[u]++; du[v]++;
}
for (int i = ; i < edge.size(); i++){
int u = edge[i].u, v = edge[i].v;
if (du[u] >= block&&du[v]>=block){
G[u].push_back(v); G[v].push_back(u);
}
if (du[u] < block){
G[u].push_back(v);
}
if (du[v] < block){
G[v].push_back(u);
}
}
scanf("%d", &q);
while (q--){
int type, pos, v; scanf("%d", &type);
if (type){
LL cnt = ; scanf("%d", &pos);
if (du[pos] < block){
for (int i = ; i < G[pos].size(); i++){
cnt += val[G[pos][i]];
}
}
else{
cnt = sum[pos];
}
printf("%I64d\n", cnt);
}
else{
scanf("%d %d", &pos, &v);
val[pos] += v;
for (int i = ; i < G[pos].size(); i++){ sum[G[pos][i]] += v; }
}
} }
//#ifdef LOCAL_TIME
// cout << "[Finished in " << clock() - start << " ms]" << endl;
//#endif
return ;
}
思路2：另一种方法。 可能由于数据弱，所以本题可以完全按照题意暴力。 不过暴力的复杂度是O(n^2)的。只是本题没卡该做法。
#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<queue>
#include<math.h>
#include<time.h>
#include<vector>
#include<iostream>
using namespace std;
typedef long long int LL;
const int MAXN = + ;
vector<int>G[MAXN];
int val[MAXN];
int main(){
//#ifdef kirito
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
//#endif
// int start = clock();
int t, n, m, q;
scanf("%d", &t);
while (t--){
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++){
G[i].clear(); val[i] = ;
}
for (int i = ; i <= m; i++){
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v); G[v].push_back(u);
}
scanf("%d", &q);
for (int i = ; i <= q; i++){
int type, pos, v;
scanf("%d", &type);
if (type){
LL cnt = ; scanf("%d", &pos);
for (int k = ; k < G[pos].size(); k++){
cnt += val[G[pos][k]];
}
printf("%I64d\n", cnt);
}
else{
scanf("%d %d", &pos, &v);
val[pos] += v;
}
} }
//#ifdef LOCAL_TIME
// cout << "[Finished in " << clock() - start << " ms]" << endl;
//#endif
return ;
}