该死该死该死！！！！！！

MD我想早睡觉你知不知道

该死该死沙比提

断开边只会影响一个块，重构这个块就行了

如果断开的点$u$是这个块$p$的根，只修改原图和块图就好了

否则，把$u$子树在块中的部分从$p$里删除，放到一个新块里。并且，这些点连到的其他块的点，也要在块图上与$p$断开与新块相连

所以我们维护一个删除边的$mark$标记

WA：一开始原图加的是双向边，通过判断$fa$防止出错..后来$fa$会变化，然后判断$fa$就失灵了应该会一直$dfs$停不下来

所以一开始$dfs$就给双向边不用的那一条打上$mark$标记就好了

ps：

1.读入挂我直接复制了PoPoQQQ大爷的因为我有一次以为是读入导致WA

2.vector好快用这道题代码交上一题比我上一题跑的都快

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;const int N=2e5+5;inline int read1(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}namespace IOStream{ const int L=1<<15; char buffer[L]; char *S,*T; char Get_Char() { if(S==T) { T=(S=buffer)+fread(buffer,1,L,stdin); if(S==T) return EOF; } return *S++; } int Get_Int() { int re=0; char c; do c=Get_Char(); while(c<'0'||c>'9'); while(c>='0'&&c<='9') re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char(); return re; } }#define read IOStream::Get_Intint n,Q,a[N],op,u,x;struct meow{ vector
           
             a; inline void set() {sort(a.begin(), a.end());} inline int count(int v) { return a.size() - (upper_bound(a.begin(), a.end(), v) - a.begin());} inline void push(int v) {a.push_back(v);} inline void insert(int v) {a.insert(lower_bound(a.begin(), a.end(), v), v);} inline void erase(int v) {a.erase(lower_bound(a.begin(), a.end(), v));} inline void replace(int x,int v) { if(x==v) return; erase(x); insert(v);} inline int size() { return a.size();}}b[N];int m, pos[N], block;struct Graph4Block{ struct edge{ int v,ne;} e[N<<1]; int cnt, h[N], ine[N], mark[N<<1]; inline void ins(int u,int v) { e[++cnt]=(edge){v,h[u]}; h[u]=cnt; ine[v]=cnt; } inline void dele(int u) {mark[ine[u]]=1;} int dfs(int u,int k) { int ans= b[u].count(k); for(int i=h[u];i;i=e[i].ne) if(!mark[i]) ans+=dfs(e[i].v, k); return ans; }}G;struct edge{ int v,ne;} e[N<<1];int cnt, h[N];inline void ins(int u,int v) { e[++cnt]=(edge){v,h[u]}; h[u]=cnt; e[++cnt]=(edge){u,h[v]}; h[v]=cnt;}int fa[N], mark[N<<1], ine[N];inline void ins1(int u,int v) { e[++cnt]=(edge){v,h[u]}; h[u]=cnt; ine[v]=cnt; fa[v]=u;}inline void dele(int u) {fa[u]=0; mark[ine[u]]=1;}void dfs(int u) { int p=pos[u]; b[p].push(a[u]); for(int i=h[u];i;i=e[i].ne) if(!mark[i]) { if(e[i].v!=fa[u]) { fa[e[i].v]=u; ine[e[i].v]=i; if(b[p].size() < block) pos[e[i].v]=p; else pos[e[i].v]=++m, G.ins(p, m); dfs(e[i].v); } else mark[i]=1; }}struct Block{ int dfs(int u,int k) { int ans= a[u]>k; for(int i=h[u];i;i=e[i].ne) if(!mark[i]) if(e[i].v!=fa[u]) { if(pos[e[i].v] == pos[u]) ans+= dfs(e[i].v, k); else ans+= G.dfs(pos[e[i].v], k); } return ans; } int Que(int u, int k) { return dfs(u, k);} void Cha(int u, int d) {b[pos[u]].replace(a[u], d); a[u]=d;} void Ins(int u, int d) { a[++n]=d; ins1(u, n); int p=pos[u]; if(b[p].size() < block) pos[n]=p, b[p].insert(a[n]); else pos[n]=++m, b[m].push(a[n]), G.ins(p, m); } void dfsSpl(int u,int p) { b[p].erase(a[u]); pos[u]=m; b[m].push(a[u]); for(int i=h[u];i;i=e[i].ne) if(!mark[i]) if(e[i].v!=fa[u]) { if(pos[e[i].v] == p) dfsSpl(e[i].v, p); else G.dele(pos[e[i].v]), G.ins(m, pos[e[i].v]); } } void Split(int u){ int p=pos[u]; if(pos[fa[u]] != p) G.dele(p); else m++, dfsSpl(u, p), b[m].set(); dele(u); }}B;int main() { freopen("in", "r", stdin); n=read(); for(int i=1;i

转载于:https://www.cnblogs.com/candy99/p/6577064.html

你可能感兴趣的文章

配置链路聚合中极小错误——失之毫厘谬以千里