河南萌新联赛2024第（四）场：河南理工大学 A

天绝 · 2024-08-10 13:20:14 · 题解

非常愉快的补完了这道了这道割点题（已红温）

题源：https://ac.nowcoder.com/acm/contest/88269/A

对于割点问题，学到一种新的方法——圆方树

圆方树最初是处理「仙人掌图」（每条边在不超过一个简单环中的无向图）的一种工具，不过发掘它的更多性质，有时我们可以在一般无向图上使用它。在圆方树中，原来的每个点对应一个 圆点，每一个点双对应一个 方点。

如图所示：

思路

在转化为圆方树后我们就可以方便地进行一系列便捷的操作，记录每个子树的点权和，在一一枚举结点即可。

注意

1. 数据可能会超过long long，可以用__int128来输出最后答案

2. 可能不只一个联通块，也就是说可能有多棵园方树，所以要标记每个结点是否有被遍历。

   代码

   #include<bits/stdc++.h>
   using namespace std;
   const int MN = 200005;
   int N, M, cnt;
   __int128 sum1,sum,dul,ans,dp[MN*2];
   long long a[MN*2];
   std::vector<int> G[MN*2], T[MN * 2];
   int dfn[MN*2], low[MN*2], dfc;
   int stk[MN*2], tp;
   void Tarjan(int u) 
   {
   low[u] = dfn[u] = ++dfc;                // low 初始化为当前节点 dfn
   stk[++tp] = u;                          // 加入栈中
   for (int v : G[u]) {                    // 遍历 u 的相邻节点
   if (!dfn[v]) {                        // 如果未访问过
   Tarjan(v);                          // 递归
   low[u] = std::min(low[u], low[v]);  // 未访问的和 low 取 min
   if (low[v] == dfn[u]) {  // 标志着找到一个以 u 为根的点双连通分量
   ++cnt;                 // 增加方点个数
   // 将点双中除了 u 的点退栈，并在圆方树中连边
   for (int x = 0; x != v; --tp) {
   x = stk[tp];
   T[cnt].push_back(x);
   T[x].push_back(cnt);
   }
   // 注意 u 自身也要连边（但不退栈）
   T[cnt].push_back(u);
   T[u].push_back(cnt);
   }
   } else
   low[u] = std::min(low[u], dfn[v]);  // 已访问的和 dfn 取 min
   }
   }
   void dfs(int u,int fa)
   {
   dp[u]=a[u];
   for (int v : T[u]) 
   {
   if(v==fa) continue;
   dfs(v,u);
   dp[u]+=dp[v];    
   }  
   }
   void print(__int128 x){
   if(x < 0){ cout<<'-';x = -x;}
   if(x > 9) print(x / 10);
   cout<<char(x % 10 + '0');
   }
   void check(int u,int fa)
   {
   __int128 posibleans=(sum1-dp[u])*(sum1-dp[u]);
   for (int v : T[u]) 
   {
   //     print(posibleans);
   //printf("\n");
   if(v==fa) continue;
   posibleans+=dp[v]*dp[v];
   check(v,u);
   } 
   if(u<=N) ans=min(ans,posibleans);
   }
   int main()
   {
   scanf("%d%d", &N, &M);
   cnt = N;  // 点双 / 方点标号从 N 开始
   for (int i = 1; i <= M; ++i) {
   int u, v;
   scanf("%d%d", &u, &v);
   G[u].push_back(v);  // 加双向边
   G[v].push_back(u);
   }
   for(int i=1;i<=N;i++) scanf("%lld",&a[i]);
   // 处理非连通图
   for (int u = 1; u <= N; ++u)
   if (!dfn[u]) 
   {
   ans=1e27;
   Tarjan(u);
   --tp;
   dfs(u,0);
   sum1=dp[u];
   sum+=sum1*sum1;
   check(u,0);
   dul=max(dul,dp[u]*dp[u]-ans);
   }
   // for(int i=1;i<=N;i++) printf("%lld  ",dp[i]);
   print(sum-dul);
   // 注意到退出 Tarjan 时栈中还有一个元素即根，将其退栈
   return 0;
   }