CF1616G Just Add an Edge

一题做了半年，什么水平？

看到这道题，先从无解的条件入手？感觉根本没办法弄啊！

但是题目中有一个很厉害的性质，就是给定的边满足 \(u < v\)，所以如果不需要我们加边，那么最终的哈密顿路径只能形如 \(1,2,3,....,n\)。先特判掉不用加边的情况，剩下的情况围绕加的这条边展开。

为了使得路径从定点开始，定点结束，创造超级源汇点 \(0,n+1\)。

假设加了 \((x,y)\) 这条边，那么相当于两条路：\(0 \rightarrow x, y \rightarrow n+1\) 不重不漏的覆盖了 \([0,n+1]\)。那么 \(y\) 左侧和 \(x\) 右侧需要满足的条件是容易处理的。

中间的路径经过的边有两种：

• 形如 \((i,i+1)\) 称为平凡边。
• 形如 \((i,j)\)，其中\(j > i + 1\) 称为特殊边。

不难发现最终的哈密顿路径由平凡边和特殊边交替构成，满足一条特殊边中间的点全是平凡边。

这启发我们针对特殊边来设计 DP 状态，设 \(f_{k,0/1}\) 表示以 \(k\) 延伸出一条特殊边，且 \(k\) 是在 \(0 \rightarrow x\) 或 \(y \rightarrow n + 1\) 上。

但是这样没有办法直接做，因为不知道从哪里开始 dp。枚举第一条特殊边的起点，可以做到 \(O(nm)\)。

但是这样是肯定过不去的。所以考虑省去枚举第一条特殊边的起点。不难发现，特殊边的起点和终点之间是可以进行组合的。注意到对于第一个 \(i\) 满足 \(i\) 和 \(i+1\) 不直接连边，一定有一条特殊边跨过了 \(i\) 和 \(i + 1\)，所以可以以 \(i\) 为起点，正反都做一次 DP，就可以求出哪些点可以作为起点或者终点了。

#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

namespace IO {
  #define isdigit(x) (x >= '0' && x <= '9')
  template<typename T>
  inline void read(T &x) {
    x = 0; char ch = getchar(); int f = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    if(f) x = -x;
  }
  template<typename T>
  inline void write(T x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
  }
  #undef isdigit
}
using namespace IO;

const int N = 1.5e5;
int n, m;
int ab[N];
vector<int> G[N];
int rl, rr;
int lim[N];
int f[N][2], tmp1[10], tmp2[10];

void clear() {
  memset(f, 0, sizeof f);
  memset(tmp1, 0, sizeof tmp1), 
  memset(tmp2, 0, sizeof tmp2);
  memset(lim, 0, sizeof lim);
  memset(ab, 0, sizeof ab);
  rl = -1, rr = 0;
}

void solve() {
  clear();
  read(n), read(m);
  for(int i = 0; i <= n + 1; ++i)
    G[i].clear();
  for(int i = 1; i <= n; ++i)
    G[0].emplace_back(i);
  for(int i = 1; i < n; ++i) 
    G[i].emplace_back(n + 1);
  for(int i = 1, u, v; i <= m; ++i) {
    read(u), read(v);
    if(v == u + 1) ab[u] = 1;
    else G[u].emplace_back(v);
  }
  ab[0] = ab[n] = 1;
  for(int i = 1; i <= n; ++i) 
    if(!ab[i]) {rl = i; break;}
  for(int i = n; i; --i)
    if(!ab[i]) {rr = i; break;}
  lim[n + 1] = n + 1;
  for(int i = n; i >= 0; --i)
    lim[i] = ab[i] ? lim[i + 1] : i;
  
  if(rl == -1) {
    printf("%lld\n",1ll * n * (n - 1) / 2);
    return;
  }

  f[rl][0] = 1, f[rl][1] = 2;
  for(int i = rl - 1; i >= 0; --i)
    for(int j : G[i]) {
      if(lim[i + 1] < j - 1) continue;
      for(int p = 0; p < 2; ++p)
        f[i][p] |= f[j - 1][p ^ 1];
    }
  for(int i = rl; i <= n; ++i) 
    for(int j : G[i]) {
      if(lim[i + 1] < j - 1) continue;
      for(int p = 0; p < 2; ++p)
        f[j - 1][p ^ 1] |= f[i][p];
    }
    
  for(int i = 0; i <= rl; ++i)
    ++tmp1[f[i][0]];
  for(int i = rr; i <= n; ++i)
    ++tmp2[f[i][0]];
  long long ans = 0;
  for(int i = 1; i <= 3; ++i)
    for(int j = 1; j <= 3; ++j)
      if(i & j) ans += 1ll * tmp1[i] * tmp2[j];
  if(rl == rr) --ans;
  printf("%lld\n",ans);
}

int main() {
  int T; read(T);
  while(T--) solve();
}