danihao123's Blog

啊啊啊我只会做水题了……

这题就是要求你只删除一条边拆爆所有的奇环，同时不能产生新的gay环，求所有可能的选择方案。

如果说只有一个奇环，那么上面的树边和非树边都是可以拆爆的。但如果有好几个奇环，那么只能选择树边了。奇环的树边部分肯定是若干链，我们只要树上差分标记一下就能求出这些链的交了。

但考虑一件事，如果一个偶环和一个奇环的树边部分相交了，那么删掉其中一边会导致新的奇环出现（证明的话考虑将环异或一下）。所以说在偶环的树边并上的边也不能取。

注意这题图可能不连通……所以要对每个连通块都DFS。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
using ll = long long;
const int maxn = 10005;
const int maxm = 20005;
struct Edge {
  int u, v;
  int id;
};
std::vector<Edge> G[maxn];
int n, m;
inline void ins_edge(int u, int v, int id) {
  G[u].push_back((Edge){u, v, id});
  G[v].push_back((Edge){v, u, id});
}

int dep[maxn], anc[maxn][15];
bool vis[maxn];
void dfs_1(int x, int fa = -1) {
  vis[x] = true;
  anc[x][0] = fa;
  for(auto &e : G[x]) {
    int v = e.v;
    if(!vis[v]) {
      dep[v] = dep[x] + 1;
      dfs_1(v, x);
    }
  }
}
int lca(int u, int v) {
  if(dep[u] < dep[v]) std::swap(u, v);
  for(int j = 14; j >= 0; j --) {
    int a = anc[u][j];
    if(a != -1 && dep[a] >= dep[v]) u = a;
  }
  if(u == v) return u;
  for(int j = 14; j >= 0; j --) {
    int a1 = anc[u][j];
    int a2 = anc[v][j];
    if(a1 != -1 && a2 != -1 && a1 != a2) {
      u = a1, v = a2;
    }
  }
  return anc[u][0];
}
bool used[maxm];
int d1[maxn], d2[maxn];
int o_cnt = 0, o_id;
void dfs_2(int x) {
  vis[x] = true;
  for(auto &e : G[x]) {
    if(used[e.id]) continue;
    used[e.id] = true;
    int v = e.v;
    if(vis[v]) {
      int l = lca(x, v);
      int dis = dep[x] + dep[v] - 2 * dep[l];
      int *d;
      if(dis & 1) {
        d = d2;
      } else {
        d = d1;
        o_cnt ++;
        if(o_cnt == 1) o_id = e.id;
      }
      d[x] ++; d[v] ++; d[l] -= 2;
    } else {
      dfs_2(v);
    }
  }
}
void dfs_3(int x) {
  vis[x] = true;
  for(auto &e : G[x]) {
    int v = e.v;
    if(!vis[v]) {
      dfs_3(v);
      d1[x] += d1[v];
      d2[x] += d2[v];
    }
  }
}
bool allow[maxm], expc[maxm];
void dfs_4(int x) {
  vis[x] = true;
  for(auto &e : G[x]) {
    int v = e.v, id = e.id;
    if(!vis[v]) {
      if(d1[v] == o_cnt) {
        allow[id] = true;
      }
      if(d2[v] > 0) {
        expc[id] = true;
      }
      dfs_4(v);
    }
  }
}
std::vector<int> ret;
void solve() {
  memset(anc, -1, sizeof(anc));
  for(int i = 1; i <= n; i ++) {
    if(!vis[i]) dfs_1(i);
  }
  for(int j = 1; (1 << j) < n; j ++) {
    for(int i = 1; i <= n; i ++) {
      int a = anc[i][j - 1];
      if(a != -1) {
        anc[i][j] = anc[a][j - 1];
      }
    }
  }
  memset(vis, 0, sizeof(vis));
  for(int i = 1; i <= n; i ++) {
    if(!vis[i]) dfs_2(i);
  }
  memset(vis, 0, sizeof(vis));
  for(int i = 1; i <= n; i ++) {
    if(!vis[i]) dfs_3(i);
  }
  memset(vis, 0, sizeof(vis));
  for(int i = 1; i <= n; i ++) {
    if(!vis[i]) dfs_4(i);
  }
  if(o_cnt == 0) {
    for(int i = 1; i <= m; i ++) ret.push_back(i);
  } else {
    for(int i = 1; i <= m; i ++) {
      if(allow[i] && (!expc[i])) {
        ret.push_back(i);
      } else if(o_cnt == 1 && o_id == i) {
        ret.push_back(i);
      }
    }
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    ins_edge(u, v, i);
  }
  solve();
  printf("%d\n", ret.size());
  bool flag = false;
  for(auto i : ret) {
    if(flag) putchar(' ');
    flag = true;
    printf("%d", i);
  }
  puts("");
  return 0;
}

很容易想到树剖直接搞一发的玩法。估计复杂度是[tex]O(nlog^2n)[/tex]的，有点吃不消，再加上会被卡常，咔嚓掉。

考虑二分答案。我们可以直接二分最终答案，那么如何验证？

假设验证谓词为[tex]C(t)[/tex]，表示通过把一条边清零可以使得用时为[tex]t[/tex]。那么所有用时大于[tex]t[/tex]的计划都要被清掉一条边。可见我们需要清零的边是所有用时大于[tex]t[/tex]的计划的边的交集中的最大边。

那么如何求交集呢？可以考虑树上差分，对于每次计划[tex](u,v)[/tex]，我们求出其最近公共祖先[tex]L[/tex]，然后对[tex]d[u][/tex]和[tex]d[v][/tex]分别加一，对[tex]d[L][/tex]则减二。随后将d上标记上推，可以求出每个点连向父亲的边被几个计划经过。易求交集。

至此方向已明确：二分答案，树上差分验证，同时我们还要用到LCA。LCA建议使用总计[tex]O(n)[/tex]的TarjanLCA离线算法，倍增也可。

代码：

/**************************************************************
    Problem: 4326
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4756 ms
    Memory:62188 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=300001,maxm=300001*2;
const int BUFSIZE=10000001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
 
int n;
namespace FastIO{
    char buf[BUFSIZE];
    int IO_tot=0;
    inline void InitFastIO(){
        fread(buf,sizeof(char),BUFSIZE-1,stdin);
    }
    inline char GetC(){
        return buf[IO_tot++];
    }
    inline int readint(){
        register int x=0;
        register char c=GetC();
        while(!isdigit(c))
            c=GetC();
        while(isdigit(c)){
            x=10*x+c-'0';
            c=GetC();
        }
        return x;
    }
    int bf[10];
    inline void putint(int x){
        register int siz=0,i;
        if(!x){
            bf[siz++]=0;
        }else{
            while(x){
                bf[siz++]=x%10;
                x/=10;
            }
        }
        for(i=siz-1;i>=0;i--)
            putchar(bf[i]+'0');
        putchar('\n');
    }
};
namespace Tree{
    int first[maxn];
    int next[maxm],to[maxm],dist[maxm];
    int tot=0;
    inline void Add_Edge(int u,int v,int d){
        tot++;
        next[tot]=first[u];
        first[u]=tot;
        to[tot]=v;
        dist[tot]=d;
    }
    int d[maxn],father[maxn];
    vector<int> hx;
    void dfs_1(int x,int fa,int dis){
        d[x]=dis;
        father[x]=fa;
        int i;
        GRAPH_REP(i,x){
            if(to[i]!=fa)
                dfs_1(to[i],x,dis+dist[i]);
        }
        hx.push_back(x);
    }
    int lazy[maxn];
    inline void ClearLazy(){
        memset(lazy,0,sizeof(lazy));
    }
    inline int DealCheck(int x){
        register int i,v,ans=0;
        REP_B(i,n){
            v=hx[i-1];
            lazy[father[v]]+=lazy[v];
        }
        REP_B(i,n){
            if(lazy[i]==x){
                ans=max(ans,d[i]-d[father[i]]);
            }
        }
        return ans;
    }
     
    // Djoin Set
    int p[maxn];
    int find_set(int x){
        if(p[x]==x)
            return x;
        else
            return p[x]=find_set(p[x]);
    }
    inline void union_set(int x,int y){
        p[find_set(y)]=find_set(x);
    }
    inline void make_set(int x){
        p[x]=x;
    }
     
    // LCA
    struct Query{
        int u,v,b;
    };
    bool vis[maxn];
    vector<Query> qs;
    vector<int> querys[maxn];
    inline void Add_Query(int x,int y,int b){
        querys[x].push_back(qs.size());
        qs.push_back((Query){x,y,b});
    }
    int res[maxn][3];
    int n;
    void LCA(int u){
        make_set(u);
        vis[u]=true;
        int i,temp;
        REP(i,querys[u].size()){
            Query& tep=qs[querys[u][i]];
            if(vis[tep.v])
                res[tep.b][2]=find_set(tep.v);
        }
        for(i=first[u];i;i=next[i]){
            temp=to[i];
            if(!vis[temp]){
                LCA(temp);
                union_set(u,temp);
            }
        }
    }
};
 
using namespace FastIO;
struct Deal{
    int u,v,lca,d;
    bool operator <(const Deal& x) const{
        return d<x.d;
    }
};
vector<Deal> V;
int m;
inline bool Check(int x){
    register int i,ideal=0,yh=V[m-1].d;
    Tree::ClearLazy();
    for(i=m-1;i>=0;i--){
        int& u=V[i].u,v=V[i].v,lca=V[i].lca,d=V[i].d;
        if(d>x){
            ideal++;
            Tree::lazy[u]++;
            Tree::lazy[v]++;
            Tree::lazy[lca]-=2;
        }else{
            break;
        }
    }
    yh-=Tree::DealCheck(ideal);
    return yh<=x;
}
int main(){
    register int i,u,v,lca,d;
    FastIO::InitFastIO();
    n=readint();
    m=readint();
    REP(i,n-1){
        u=readint();
        v=readint();
        d=readint();
        Tree::Add_Edge(u,v,d);
        Tree::Add_Edge(v,u,d);
    }
    REP(i,m){
        u=readint();
        v=readint();
        Tree::Add_Query(u,v,i);
        Tree::Add_Query(v,u,i);
        Tree::res[i][0]=u;
        Tree::res[i][1]=v;
    }
    Tree::dfs_1(1,0,0);
    Tree::LCA(1);
    REP(i,m){
        u=Tree::res[i][0];
        v=Tree::res[i][1];
        lca=Tree::res[i][2];
        d=Tree::d[u]+Tree::d[v]-2*Tree::d[lca];
        V.push_back((Deal){u,v,lca,d});
    }
    sort(V.begin(),V.end());
    u=0;
    v=V[m-1].d+1;
    while(u<v){
        d=u+(v-u)/2;
        if(Check(d))
            v=d;
        else
            u=d+1;
    }
    putint(u);
    return 0;
}