题解：P11287 [COTS 2017] 影响 Utjecaj

从原图中去掉所有关键点得到若干连通块，把这些连通块变成新的点，新点权为连通块的点权和，新点再与关键点相连得到一个新的图。 于是问题转化为在新的图上修改点权、查询与某个点相邻的点（包含自己）的点权和。

考虑根号分治。设新图边数为 m，度数超过 \sqrt{m} 的非关键点称为“大点”，显然“大点”只有 O(\sqrt{m}) 个。 维护关键点的影响力， 修改点权时，若修改“大点”的点权，那么给这个点打上标记，否则直接加到相邻的关键点的影响力上。 查询时，答案就是我们维护的这个点的影响力加上相邻“大点”的标记。

时间复杂度 O(n+q\sqrt{m})。

#include<bits/stdc++.h>
using I=long long;
template<class T>using V=std::vector<T>;
template<class T,I N>using A=std::array<T,N>;
int main(){
  std::cin.tie(0)->sync_with_stdio(0);
  I n,m;std::cin>>n>>m;
  V<I>key(n);for(I&e:key)std::cin>>e;
  V<I>a(n);for(I&e:a)std::cin>>e;
  V<V<I>>g(n);
  for(I i=0;i<m;i++){
    I u,v;std::cin>>u>>v;u--;v--;
    g[u].push_back(v);g[v].push_back(u);
  }

  I z=0;V<I>bl(n,-1),b;
  for(I i=0;i<n;i++)if(key[i])bl[i]=z++,b.push_back(a[i]);
  V<std::unordered_set<I>>g2(z);I nk=z;V<I>ww(nk);
  auto dfs=[&](auto&&dfs,I u,I c)->void{
    bl[u]=c;b[c]+=a[u];
    for(I v:g[u]){
      if(bl[v]==-1)dfs(dfs,v,c);
      else if(bl[v]!=c)g2[c].insert(bl[v]),g2[bl[v]].insert(c);
    }
  };
  for(I i=0;i<n;i++){
    if(bl[i]==-1)g2.push_back(std::unordered_set<I>()),b.push_back(0),dfs(dfs,i,z++);
  }
  for(I i=0;i<nk;i++){
    ww[i]=b[i];
    for(I v:g2[i])if(v>=nk)ww[i]+=b[v];
  }

  I sd=0;for(I i=0;i<z;i++)sd+=g2[i].size();
  I blk=sqrt(sd);V<I>big,tag(n);
  for(I i=0;i<z;i++)if(g2[i].size()>blk)big.push_back(i);

  I q;std::cin>>q;
  while(q--){
    I o,x,y;std::cin>>o>>x;x--;I u=bl[x];
    if(o==1){
      std::cin>>y;
      if(u<nk)ww[u]+=y-a[x];
      else if(g2[u].size()>blk)tag[u]+=y-a[x];
      else for(I v:g2[u])if(v<nk)ww[v]+=y-a[x];
      a[x]=y;
    }else{
      I w=ww[u];
      for(I i:big)if(g2[u].count(i))w+=tag[i];
      std::cout<<w<<'\n';
    }
  }
  return 0;
}