N个点，M条无向边。现在有Q组操作，一种是给 i号点增加能量，一种是询问 i号点相邻点的能量和(点间有多条边就算两次)。
据说暴力能过，但还是用这题学习了一下 点分块 。 度数不超过 sqrt(M) 的为 "轻点"， 否则为 "重点"，"轻点"可以指向(连向)这两种点，但"重点"只能指向(连向)"重点" 。val[i]表示i号点能量，sum[i]维护i号点所有相邻的能量。"增加能量"时更新i号点相邻点j的sum[j]，查询时"轻点"暴力搜，"重点"直接O(1)返回 sum[i]即可。
修改时，"轻点"们可以修改"重点"，"重点"可以修改"重点"，"重点"的sum[]是被维护的，而"轻点"只有sqrt(M)条边，爆搜没问题。
ps : 似乎"重点"出度不超过 2*sqrt(M)，未证明。
#include <bits/stdc++.h>
using namespace std;
#define fst first
#define scd second
#define pb(x) push_back((x))
#define mkp(x,y) make_pair((x),(y))
#define ist(x) insert((x))
typedef long long ll;
typedef pair<int ,int > pii;
typedef pair<ll ,ll > pll;
typedef vector< int > vi;
ll gcd(ll a,ll b){ return b==?a:gcd(b,a%b);}
ll qPow(ll a,ll b,ll mod){ ll ret=1ll;while(b){ if(b&) ret=ret*a%mod;a=a*a%mod;b>>=;} return ret; } const int maxn=;
int degree[maxn];
vi G[maxn];
ll val[maxn];
ll sum[maxn];
pii bian[maxn];
int bound; void addedge(int u,int v){
if(degree[u]<=bound) G[u].pb(v);
else if(degree[v]>bound) G[u].pb(v);
} int main(){
int T;
scanf("%d",&T);
while(T--) {
int N,M;
scanf("%d%d",&N,&M);
for(int i=;i<=N;++i){
degree[i]=;
G[i].clear();
val[i]=0ll;
sum[i]=0ll;
}
for(int i=;i<=M;++i){
int u,v;
scanf("%d%d",&u,&v);
pii tmp=mkp(u,v);
degree[u]++,degree[v]++;
bian[i]=tmp;
}
bound=sqrt(M);
for(int i=;i<=M;++i)
{
int u=bian[i].fst,v=bian[i].scd;
addedge(u,v);
addedge(v,u);
}
int Q;
scanf("%d",&Q);
for(int i=;i<Q;++i){
int op;
scanf("%d",&op);
if(op){
int u;scanf("%d",&u);
if(degree[u]>bound) printf("%I64d\n",sum[u]);
else{
ll ans=0ll;
for(auto to: G[u]) {
ans+=val[to];
}
printf("%I64d\n",ans);
}
}
else{
int u,w;scanf("%d%d",&u,&w);
val[u]+=1ll*w;
for(auto to: G[u]){
sum[to]+=1ll*w;
}
}
}
}
return ;
}
分摊复杂度，点分块。