https://vjudge.net/problem/HDU-4467
大概就是，设一个块大小T
对于度数<=T的点，设为1类点，在改变颜色的时候暴力查询与其相邻点，更新答案
对于度数>T的点，设为2类点，分别维护与其相邻的颜色为0/1的点之间的边权和（记录与每个点相连的所有2类点，然后在任意点(注意2类点也要)改变颜色时维护一下与其相连2类点的这个值），改变颜色的时候根据维护的值O(1)可以计算出对答案的修改
说的再简单一点，1类点由自身去更新其他，2类点由其他去更新自身。。复杂度很容易发现是根号级别的（T=sqrt(m)）
但是要注意，重边一定要去。。。不然可以被卡到$n^2$
错误记录：
1.没有在改变2类点颜色时改变相连其他2类点维护的值
2.没有去重边
3.d[a],d[b]和a,b没有极其仔细地区分
//#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#include<map>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define N 100000
struct E
{
int to,nxt;ll d;
}e[*N+];
int f1[N+],ne;
int TT,n,m,mm,d[N+];
int in[N+],sz,q;
//1类点:in[i]<=sz;2类点:in[i]>sz
ll a1[N+][];
//a1[i][j]:i为2类点,i与相邻的颜色为j的点之间的所有边的权值和
//int num[100100];
char tmp[];
vector<int> ss[N+];//ss[i]:i点到相邻的2类点的边
ll ans[];//ans[0]:00边答案;ans[1]:11边答案;ans[2]:01边答案
map<pii,pii> ma;
ll &gg(int a,int b)
{
if(a==&&b==) return ans[];
if(a==&&b==) return ans[];
return ans[];
}
int main()
{
int a,b,c,i,k;pii t;
while(scanf("%d%d",&n,&m)==)
{
TT++;mm=;//num[0]=0;
memset(f1,,sizeof(f1));ne=;ma.clear();
memset(in,,sizeof(in));ans[]=ans[]=ans[]=;
memset(a1,,sizeof(a1));
for(i=;i<=n;i++) scanf("%d",&d[i]);
for(i=;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(a>b) swap(a,b);
if(ma.count(mp(a,b)))
{
t=ma[mp(a,b)];
e[t.fi].d+=c;e[t.se].d+=c;
}
else
{
e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;e[ne].d=c;
e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;e[ne].d=c;
in[a]++;in[b]++;
ma[mp(a,b)]=mp(ne-,ne);mm++;
}
gg(d[a],d[b])+=c;
}
sz=sqrt(*mm);
for(i=;i<=n;i++)
if(in[i]>sz)
{
//num[++num[0]]=i;
for(k=f1[i];k;k=e[k].nxt)
a1[i][d[e[k].to]]+=e[k].d;
}
for(i=;i<=n;i++)
{
ss[i].clear();
for(k=f1[i];k;k=e[k].nxt)
if(in[e[k].to]>sz)
ss[i].pb(k);
}
scanf("%d",&q);
printf("Case %d:\n",TT);
while(q--)
{
scanf("%s",tmp);
if(tmp[]=='A')
{
scanf("%d%d",&a,&b);
printf("%lld\n",gg(a,b));
}
else
{
scanf("%d",&a);
if(in[a]<=sz)
{
for(k=f1[a];k;k=e[k].nxt)
{
b=e[k].to;
gg(d[a],d[b])-=e[k].d;
if(in[b]>sz) a1[b][d[a]]-=e[k].d;
}
d[a]^=;
for(k=f1[a];k;k=e[k].nxt)
{
b=e[k].to;
gg(d[a],d[b])+=e[k].d;
if(in[b]>sz) a1[b][d[a]]+=e[k].d;
}
}
else
{
for(i=;i<ss[a].size();i++)
a1[e[ss[a][i]].to][d[a]]-=e[ss[a][i]].d;
gg(d[a],)-=a1[a][];gg(d[a],)-=a1[a][];
d[a]^=;
gg(d[a],)+=a1[a][];gg(d[a],)+=a1[a][];
for(i=;i<ss[a].size();i++)
a1[e[ss[a][i]].to][d[a]]+=e[ss[a][i]].d;
}
}
}
}
return ;
}