[UOJ 207]共价大爷游长沙

给你一棵\(n\)个点的树，要求你滋磁以下操作（共\(m\)次）：

  • 对于给定的点对\((x, y)\)和\((u, v)\)，删除边\((x, y)\)，添加边\((u, v)\)。保证操作时\((u, v)\)存在，并且保证操作后的图还是一棵树。
  • 向集合\(S\)中加入一个点对\((u, v)\)。
  • 从\(S\)中删除一个点对。
  • 给定一条边\((x, y)\)（保证在当前树中存在），求问是否所有\((u, v)\in S\)都满足\(u\)到\(v\)的路径经过了\((x, y)\)。

\(1\leq n\leq 10^5, 1\leq m\leq 300000\)。

继续阅读

题解 uoj LCT DFS树 Comments(0) 2018年9月03日 14:32

[CF 19E]Fairy

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

这题就是要求你只删除一条边拆爆所有的奇环，同时不能产生新的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;
}

题解 Codeforces DFS树 树上差分 Comments(0) 2018年3月09日 10:10

[BZOJ 2115][Wc2011]Xor

这个可以有啊（赞赏）！

我们可以发现如果两点间如果有多条路径，那么任意两条路径在一个简单环里。

然后我们还发现，如果说是一个路径，一个环和这个路径有交边，那么走这个环走很多次没有意义（其实相当于从环的两边选一边走）。

然后这样可以发现，用$1$到$n$的路径来异或一个环，可以得到新的一条$1$到$n$的路径。

这样我们可以用DFS树来求出图上所有简单环的异或和，求出其线性基，然后随便找条$1$到$n$的路径，问题就变成了求这条路径和那个线性基的异或和最大是多少。然后这就是线性基乱搞好了……

代码：

/**************************************************************
    Problem: 2115
    User: danihao123
    Language: C++
    Result: Accepted
    Time:652 ms
    Memory:6544 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <vector>
typedef long long ll;
const int maxn = 50005;
const int maxm = maxn << 2;
int first[maxn];
int next[maxm], to[maxm];
ll dist[maxm]; int rev[maxm];
int add_edge(int u, int v, ll d) {
  static int cnt = 0;
  cnt ++;
  next[cnt] = first[u]; first[u] = cnt;
  to[cnt] = v; dist[cnt] = d;
  return cnt;
}
void ins_edge(int u, int v, ll d) {
  int e1 = add_edge(u, v, d);
  int e2 = add_edge(v, u, d);
  rev[e1] = e2; rev[e2] = e1;
}
 
const int maxb = 61;
ll T[maxb];
void insert(ll x) {
  for(int i = 60; i >= 0; i --) {
    if(!x) break;
    if((x & (1LL << i)) == 0) continue;
    if(T[i]) {
      x ^= T[i];
    } else {
      for(int j = i - 1; j >= 0; j --) {
        if(x & (1LL << j)) {
          x ^= T[j];
        }
      }
      for(int j = i + 1; j < maxb; j ++) {
        if(T[j] & (1LL << i)) {
          T[j] ^= x;
        }
      }
      T[i] = x; break;
    }
  }
}
ll sum[maxn];
bool vis[maxn], used[maxm];
void dfs(int x, ll s) {
  vis[x] = true; sum[x] = s;
  for(int i = first[x]; i; i = next[i]) {
    if(used[i]) continue;
    int v = to[i];
    used[i] = used[rev[i]] = true;
    if(vis[v]) {
      insert((s ^ sum[v]) ^ dist[i]);
    } else {
      dfs(v, s ^ dist[i]);
    }
  }
}
 
#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
  int n, m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int u, v; ll d;
    scanf("%d%d", &u, &v); scanf(LO, &d);
    ins_edge(u, v, d);
  }
  dfs(1, 0LL);
  ll ret = sum[n];
  for(int i = 60; i >= 0; i --) {
    if(!T[i]) continue;
    if(!(ret & (1LL << i))) {
      ret ^= T[i];
    }
  }
  printf(LO, ret); puts("");
  return 0;
}

题解 bzoj wc 线性基 DFS树 Comments(0) 2018年2月28日 10:09

[LibreOJ 6238][Baltic2015]Network

LibreOJ真是好用（以后尽可能少用BZOJ）

这题我觉得真是个意识流神题。

考虑所有度数为1的点（姑且称为叶子），这些点是一定要向外连边的（只要有一个度数为1的树边不在一个环中，肯定就出桥了）。

那是否可以只在这种叶子之间连边？答案是肯定的。假设叶子上形成了足够多的环，那么上面的边可以随便上。

那是否叶子配对连边就行了（这说明答案是\(\lceil \frac{l}{2}\rceil\)，其中\(l\)是叶子的数目）？答案也是肯定的。但这种方案里显然两个结点间有新边则两点不可能在根的同一棵子树里。

然后就有一种乱搞做法：找到一个根使得每个子树的叶子数都不超过总数的一半（这种点很显然存在），然后从这个根开始DFS，把所有叶子按照DFS序排序一遍，前一半向后一半依次连边。如果叶子数目是奇数，那么最后一个可以随便连。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <queue>
#include <set>
#include <vector>
using std::vector;
const int maxn = 500005;
vector<int> G[maxn];

int n;
int leaves[maxn];
vector<int> L;
int leavenum = 0;
void calc_leave(int x, int fa = 0) {
  if(int(G[x].size()) == 1) {
    leaves[x] = 1; L.push_back(x);
    leavenum ++;
  }
  for(auto v : G[x]) {
    if(v != fa) {
      calc_leave(v, x);
      leaves[x] += leaves[v];
    }
  }
}
int gen_rt(int x, int fa = 0) {
  for(auto v : G[x]) {
    if(v != fa && leaves[v] * 2 >= leavenum) {
      return gen_rt(v, x);
    }
  }
  return x;
}
int dfn[maxn];
void calc_dfn(int x, int fa = 0) {
  static int cnt = 0;
  dfn[x] = ++ cnt;
  for(auto v : G[x]) {
    if(v != fa) {
      calc_dfn(v, x);
    }
  }
}

bool cmp(const int &x, const int &y) {
  return dfn[x] < dfn[y];
}
int main() {
  scanf("%d", &n);
  for(int i = 0; i < n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    G[u].push_back(v); G[v].push_back(u);
  }
  calc_leave(1);
  int rt = gen_rt(1);
  calc_dfn(rt);
  sort(L.begin(), L.end(), cmp);
  printf("%d\n", (leavenum + 1) / 2);
  int half = leavenum / 2;
  for(int i = 0; i < half; i ++) {
    printf("%d %d\n", L[i], L[i + half]);
  }
  if(1 & leavenum) {
    printf("%d %d\n", L[half - 1], L[leavenum - 1]);
  }
  return 0;
}

题解 loj Baltic DFS树 Comments(0) 2018年2月14日 22:50