[HNOI2015]接水果[整体二分]

[HNOI2015]接水果

给出一个树上路径集合\(S\) 多次询问\(x,y\)中的\(k\)小值

如果你问我数列上那么我会

树上的话树上差分了吧直接？…

令 \(st_x<st_y\)

1.假设 \(LCA(x,y) == x\)

（学过树的人都知道不可能等于y）

然后树剖乱跳到一个路径上不在 \(x->y\) 上的 \(z\) 就可以了

\([1,st_z-1] or [st_z+1,n]\)

2.1假设不成立…

那么一个点在 \([st_x,ed_x]\) , 另一个在 \([st_y,ed_y]\) 里面就可以了…

#include <bits/stdc++.h>

#define rep(a , b , c) for(register int a = b ; a <= c ; ++ a)

#define Rep(a , b , c) for(register int a = b ; a >= c ; -- a)

#define go(u) for(register int i = G.head[u] , v = G.to[i] , w = G.dis[i] ; i ; v = G.to[i = G.nxt[i]] , w = G.dis[i])

using namespace std ;

inline int read() {

  int x = 0 ; bool f = 1 ; char c = getchar() ;

  while(c < 48 || c > 57) { if(c == '-') f = 0 ; c = getchar() ; }

  while(c > 47 && c < 58) { x = (x << 1) + (x << 3) + (c & 15) ; c = getchar() ; }

  return f ? x : -x ;

}

template <class T> inline void print(T x , char c = '\n') {

  static char st[100] ; int stp = 0 ;

  if(! x) { putchar('0') ; }

  if(x < 0) { x = -x ; putchar('-') ; }

  while(x) { st[++ stp] = x % 10 ^ 48 ; x /= 10 ; }

  while(stp) { putchar(st[stp --]) ; } putchar(c) ;

}

template <class T> void cmax(T & x , T y) { x < y ? x = y : 0 ; }

template <class T> void cmin(T & x , T y) { x > y ? x = y : 0 ; }

const int _N = 1e6 + 10 ;

struct Group {

  int head[_N] , nxt[_N << 1] , to[_N] , dis[_N] , cnt = 1 ;

  void init() { memset(head , 0 , sizeof(head)) ; cnt = 1 ; }

  inline void add(int u , int v , int w = 1) { nxt[++ cnt] = head[u] ; to[cnt] = v ; dis[cnt] = w ; head[u] = cnt ; }

} ;

const int N = 4e4 + 10  ;

typedef int arr[N] ;

int n , m , Q , len , cnt ;

arr ans , b , sz , fa , d , son , top , st , ed ;

struct Qry {

  int opt , x , l , r , k , v , id ;

  bool operator < (const Qry & other) const { if(x != other.x) return x < other.x ; return opt < other.opt ; }

} q[N << 3] , q1[N << 3] , q2[N << 3] ;

Group G ;

void dfs(int u) { sz[u] = 1 ; go(u) if(v != fa[u]) { d[v] = d[u] + 1 ; fa[v] = u ; dfs(v) ; sz[u] += sz[v] ; if(sz[v] > sz[son[u]]) son[u] = v ;} }

int idx = 0 ;

void dfs(int u , int t) { st[u] = ++ idx ; top[u] = t ; if(son[u]) dfs(son[u] , t) ; go(u) if(v != fa[u] && v != son[u]) dfs(v , v) ; ed[u] = idx ; }

inline int Lca(int x , int y) { while(top[x] != top[y]) { if(d[top[x]] < d[top[y]]) swap(x , y) ; x = fa[top[x]] ; } return d[x] < d[y] ? x : y ; }

inline int getson(int x , int y) { while(top[x] != top[y]) { if(fa[top[x]] == y) return top[x] ; x = fa[top[x]] ; } return son[y] ; }

struct BIT {

  int c[N] ; inline int low(int x) { return x & -x ; }

  inline void add(int x , int y) { for( ; x <= n ; x += low(x)) c[x] += y ; }

  inline int query(int x) { int ans = 0 ; for( ; x ; x ^= low(x)) ans += c[x] ; return ans ; }

} t ;

void solve(int L , int R , int l , int r) {

  if(L > R) return ;

  if(l == r) { rep(i , L , R) if(q[i].opt == 2) { ans[q[i].id] = l ; } return ; }

  int mid = l + r >> 1 , cnt1 = 0 , cnt2 = 0 ;

  rep(i , L , R) {

    if(q[i].opt == 1) {

      if(q[i].k <= mid) { t.add(q[i].l , q[i].v) ; t.add(q[i].r + 1 , -q[i].v) ; q1[++ cnt1] = q[i] ; }

      else q2[++ cnt2] = q[i] ;

    }

    else { int val = t.query(q[i].l) ; if(q[i].k <= val) { q1[++ cnt1] = q[i] ; } else { q[i].k -= val ; q2[++ cnt2] = q[i] ; } }

  }

  rep(i , 1 , cnt1) q[L + i - 1] = q1[i] ; rep(i , 1 , cnt2) q[L + i + cnt1 - 1] = q2[i] ;

  solve(L , L + cnt1 - 1 , l , mid) ; solve(L + cnt1 , R , mid + 1 , r) ;

}

signed main() {

  n = read() ; m = read() ; Q = read() ;

  rep(i , 2 , n) { int x = read() , y = read() ; G.add(x , y) ; G.add(y , x) ; } dfs(1) ; dfs(1 , 1) ;

  rep(i , 1 , m) {

    int x = read() , y = read() , k = read() ; b[++ len] = k ;

    if(st[x] > st[y]) swap(x , y) ;

    int lca = Lca(x , y) ;

    if(lca == x) {

      int z = getson(y , x) ;

      if(st[z] > 1) { q[++ cnt] = { 1 , 1 , st[y] , ed[y] , k , 1 , 0 } ; q[++ cnt] = { 1 , st[z] , st[y]  , ed[y] , k , -1 , 0 } ; }

      if(ed[z] < n) { q[++ cnt] = { 1 , st[y] , ed[z] + 1 , n , k , 1 , 0 } ; q[++ cnt] = { 1 , ed[y] + 1 , ed[z] + 1 , n , k , -1 , 0 } ; }

    }

    else { q[++ cnt] = { 1 , st[x] , st[y] , ed[y] , k , 1 , 0 } ; q[++ cnt] = { 1 , ed[x] + 1 , st[y] , ed[y] , k , -1 , 0 } ; }

  } sort(b + 1 , b + len + 1) ; len = unique(b + 1 , b + len + 1) - b - 1 ;

  rep(i , 1 , cnt) q[i].k = lower_bound(b + 1 , b + len + 1 , q[i].k) - b ;

  rep(i , 1 , Q) {

    int x = read() , y = read() , k = read() ;

    if(st[x] > st[y]) swap(x , y) ;

    q[++ cnt] = { 2 , st[x] , st[y] , 0 , k , 0 , i } ;

  } sort(q + 1 , q + cnt + 1) ; solve(1 , cnt , 1 , len) ;

  for(int i = 1 ; i <= Q ; i ++) print(b[ans[i]]) ;

  return 0 ;

}

巴特西

[HNOI2015]接水果[整体二分]

最新文章

热门文章