4538: [Hnoi2016]网络

分析：

　　整体二分。

　　对于一次操作，可以二分一个答案mid，判断权值大于mid的路径是否全部经过这个点。如果是，那么这次询问的答案在[l,mid-1]之间，否则在[mid,r]之间。

　　判断是否所有的路径经过一个点：等价于数经过这个点的路径条数，对于一条路径(u->v)，可以在u,v处+1，在lca处-1，在fa[lca]处-1，然后询问一个点的子树和即可。

　　多次询问，整体二分即可。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              using namespace std;typedef long long LL;inline int read() { int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;}const int N = 200005;struct Data { int ty, a, b, v, c; } A[N], B[N], C[N];struct Edge { int to, nxt; } e[N << 1];int head[N], f[N][20], dfn[N], dep[N], siz[N], ans[N], En, Index;inline void add_edge(int u,int v) { ++En; e[En].to = v, e[En].nxt = head[u]; head[u] = En; ++En; e[En].to = u, e[En].nxt = head[v]; head[v] = En;}int LCA(int u,int v) { if (dep[u] < dep[v]) swap(u, v); int d = dep[u] - dep[v]; for (int i = 18; ~i; --i) if ((d >> i) & 1) u = f[u][i]; if (u == v) return u; for (int i = 18; ~i; --i) if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i]; return f[u][0];}void dfs(int u) { for (int j = 1; j <= 18; ++j) f[u][j] = f[f[u][j - 1]][j - 1]; dep[u] = dep[f[u][0]] + 1; dfn[u] = ++Index; siz[u] = 1; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v == f[u][0]) continue; f[v][0] = u; dfs(v); siz[u] += siz[v]; }}struct Bit{ int sum[N << 1], n; void clear() { memset(sum, 0, sizeof(sum)); } void update(int p,int v) { if (p == 0) return ; for (; p <= n; p += (p & (-p))) sum[p] += v; } int query(int p) { int ans = 0; for (; p; p -= (p & (-p))) ans += sum[p]; return ans; } int Ask(int l,int r) { return query(r) - query(l - 1); }}bit;void add(Data &A,int ty) { ty = ty ? -1 : 1; bit.update(dfn[A.a], ty); bit.update(dfn[A.b], ty); bit.update(dfn[A.c], -ty); bit.update(dfn[f[A.c][0]], -ty);}void solve(int l,int r,int H,int T) { if (H > T) return ; if (l == r) { for (int i = H; i <= T; ++i) if (A[i].ty == 2) ans[A[i].b] = l; return ; } int mid = (l + r + 1) >> 1, cl = H, cr = T, now = 0; for (int i = H; i <= T; ++i) { if (A[i].ty <= 1) { if (A[i].v < mid) B[cl ++] = A[i]; else add(A[i], A[i].ty), B[cr --] = A[i], now += (A[i].ty ? -1 : 1); } else { int t = bit.Ask(dfn[A[i].a], dfn[A[i].a] + siz[A[i].a] - 1); if (t == now) B[cl ++] = A[i]; else B[cr --] = A[i]; } } for (int i = H; i <= T; ++i) if (A[i].ty <= 1 && A[i].v >= mid) add(A[i], !A[i].ty); for (int i = H; i < cl; ++i) A[i] = B[i]; for (int i = cl; i <= T; ++i) A[i] = B[T - i + cl]; solve(l, mid - 1, H, cl - 1); solve(mid, r, cl, T);}int main() { int n = read(), m = read(), mx = 0, id = 0, tot = 0, now = 0; bit.n = n; for (int i = 1; i < n; ++i) { int u = read(), v = read(); add_edge(u, v); } dfs(1); for (int i = 1; i <= m; ++i) { int opt = read(); if (opt == 0) { int u = read(), v = read(), w = read(), z = LCA(u, v); A[i] = (Data){opt, u, v, w, z}; mx = max(mx, w); } else if (opt == 1) { int t = read(); A[i] = A[t]; A[i].ty = 1; } else if (opt == 2) { int x = read(); ++id; A[i] = (Data){ 2, x, id, 0, 0}; } } for (int i = 1; i <= m; ++i) { if (A[i].ty <= 1) add(A[i], A[i].ty), now += (A[i].ty ? -1 : 1), B[++tot] = A[i]; else { if (bit.Ask(dfn[A[i].a], dfn[A[i].a] + siz[A[i].a] - 1) == now) ans[A[i].b] = -1; else B[++tot] = A[i]; } } for (int i = 1; i <= tot; ++i) A[i] = B[i]; bit.clear(); solve(-1, mx, 1, tot); for (int i = 1; i <= id; ++i) printf("%d\n", ans[i]); return 0;}

转载于:https://www.cnblogs.com/mjtcn/p/10447354.html

你可能感兴趣的文章