CSP-S 模拟 19/10/26

继续优化：发现线段树的做法还是不优秀 考虑到要让每个点询问的时候把子树做完，显然暴力就是先清空然后把子树贡献做一次 然后发现可以对时间差分就完了，出子树的时候显然已经把子树做完，与进子树的时候做差即可

反思：本题暴零并不在意料之外

#include#define cs constusing namespace std;namespace IO{ const int Rlen=1<<22|1; char buf[Rlen],*p1,*p2; inline char gc(){ return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++; } template inline T Read(){ char c;T x; while(!isdigit(c=gc()));x=c^48; while( isdigit(c=gc())) x=(x+(x<<2)<<1)+(c^48); return x; } inline int read() {return Read();}} using namespace IO;cs int N = 1e6 + 5;#define pb push_backint n, ans[N];typedef pair pi;#define mk make_pairvector v[N]; // 差分询问 namespace seg{ int rt[N], node, sum[N * 30], ls[N * 30], rs[N * 30]; stack bin; int newnode(){ int x = 0; if(bin.size()) x = bin.top(), bin.pop(); else x = ++node; sum[x] = ls[x] = rs[x] = 0; return x; } #define mid ((l+r)>>1) void ins(int &x, int l, int r, int p, int v){ if(!x) x = newnode(); sum[x] += v; if(l == r) return; if(p <= mid) ins(ls[x], l, mid, p, v); else ins(rs[x], mid + 1, r, p, v); } int merge(int x, int y){ if(!x || !y) return x | y; sum[x] += sum[y]; bin.push(y); ls[x] = merge(ls[x], ls[y]); rs[x] = merge(rs[x], rs[y]); return x; } int query(int x, int l, int r, int L, int R){ if(!x) return 0; if(L<=l && r<=R) return sum[x]; int ans = 0; if(L<=mid) ans += query(ls[x], l, mid, L, R); if(R>mid) ans += query(rs[x], mid+1, r, L, R); return ans; }}using namespace seg;struct GraphA{ int first[N], nxt[N << 1], to[N << 1], w[N << 1], tot; void add(int x, int y, int z){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y, w[tot] = z; } int dep[N], fa[N], siz[N], son[N], top[N], idx[N]; void dfs(int u, int f){ siz[u] = 1; for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == f) continue; dep[t] = dep[u] + 1; fa[t] = u; idx[t] = w[i]; dfs(t, u); siz[u] += siz[t]; if(siz[t] > siz[son[u]]) son[u] = t; } } void dfs2(int u, int tp){ top[u] = tp; if(son[u]) dfs2(son[u], tp); for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa[u] || t == son[u]) continue; dfs2(t, t); } } int lca(int x, int y){ while(top[x] ^ top[y]){ if(dep[top[x]] < dep[top[y]]) swap(x, y); x = fa[top[x]];} return dep[x] < dep[y] ? x : y; } void putag(int x, int y){ v[x].pb(x); v[y].pb(x); v[lca(x, y)].pb(-x); }}A;struct GraphB{ int first[N], nxt[N << 1], to[N << 1], tot; void add(int x, int y){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y; } int in[N], ed[N], sign; int dep[N], fa[N], siz[N], son[N], top[N]; void dfs(int u, int f){ in[u] = ++sign; siz[u] = 1; for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == f) continue; dep[t] = dep[u] + 1; fa[t] = u; A.putag(t, u); dfs(t, u); siz[u] += siz[t]; if(siz[t] > siz[son[u]]) son[u] = t; } ed[u] = sign; } void dfs2(int u, int tp){ top[u] = tp; if(son[u]) dfs2(son[u], tp); for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa[u] || t == son[u]) continue; dfs2(t, t); } } int lca(int x, int y){ while(top[x] ^ top[y]){ if(dep[top[x]] < dep[top[y]]) swap(x, y); x = fa[top[x]];} return dep[x] < dep[y] ? x : y; } void modify(int rx, int u, int v){ seg::ins(seg::rt[rx], 1, n, in[u], v); if(ed[u] < n) seg::ins(seg::rt[rx], 1, n, ed[u] + 1, -v); } int ask(int rx, int x){ return seg::query(seg::rt[rx], 1, n, 1, x); } int query(int u, int v){ return ask(u, in[u]) + ask(u, in[v]) - 2 * ask(u, in[lca(u, v)]); }}B;void Solve(int u, int fa){ for(int i = A.first[u]; i; i = A.nxt[i]){ int t = A.to[i]; if(t == fa) continue; Solve(t, u); seg::rt[u] = seg::merge(seg::rt[u], seg::rt[t]); } for(int i = 0; i < v[u].size(); i++){ int t = v[u][i]; if(t > 0) B.modify(u, t, 1); else B.modify(u, -t, -2); } if(u == 1) return; ans[A.idx[u]] = B.query(u, fa);}int main(){ n = read(); for(int i = 1; i < n; i++){ int x = read(), y = read(); A.add(x, y, i); A.add(y, x, i); } A.dep[1] = 1; A.dfs(1, 0); A.dfs2(1, 1); for(int i = 1; i < n; i++){ int x = read(), y = read(); B.add(x, y); B.add(y, x); } B.dep[1] = 1; B.dfs(1, 0); B.dfs2(1, 1); Solve(1, 0); for(int i = 1; i < n; i++) cout << ans[i] << " "; return 0;}

// BIT#include#define cs constusing namespace std;namespace IO{ const int Rlen=1<<22|1; char buf[Rlen],*p1,*p2; inline char gc(){ return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++; } template inline T Read(){ char c;T x; while(!isdigit(c=gc()));x=c^48; while( isdigit(c=gc())) x=(x+(x<<2)<<1)+(c^48); return x; } inline int read() {return Read();}} using namespace IO;cs int N = 1e6 + 5;#define pb push_backint n, ans[N];typedef pair pi;#define mk make_pairvector v[N]; // 差分询问 struct GraphA{ int first[N], nxt[N << 1], to[N << 1], w[N << 1], tot; void add(int x, int y, int z){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y, w[tot] = z; } int dep[N], fa[N], siz[N], son[N], top[N], idx[N]; void dfs(int u, int f){ siz[u] = 1; for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == f) continue; dep[t] = dep[u] + 1; fa[t] = u; idx[t] = w[i]; dfs(t, u); siz[u] += siz[t]; if(siz[t] > siz[son[u]]) son[u] = t; } } void dfs2(int u, int tp){ top[u] = tp; if(son[u]) dfs2(son[u], tp); for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa[u] || t == son[u]) continue; dfs2(t, t); } } int lca(int x, int y){ while(top[x] ^ top[y]){ if(dep[top[x]] < dep[top[y]]) swap(x, y); x = fa[top[x]];} return dep[x] < dep[y] ? x : y; } void putag(int x, int y){ v[x].pb(x); v[y].pb(x); v[lca(x, y)].pb(-x); }}A;struct GraphB{ int first[N], nxt[N << 1], to[N << 1], tot; void add(int x, int y){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y; } int in[N], ed[N], sign; int dep[N], fa[N], siz[N], son[N], top[N]; void dfs(int u, int f){ in[u] = ++sign; siz[u] = 1; for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == f) continue; dep[t] = dep[u] + 1; fa[t] = u; A.putag(t, u); dfs(t, u); siz[u] += siz[t]; if(siz[t] > siz[son[u]]) son[u] = t; } ed[u] = sign; } void dfs2(int u, int tp){ top[u] = tp; if(son[u]) dfs2(son[u], tp); for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa[u] || t == son[u]) continue; dfs2(t, t); } } int lca(int x, int y){ while(top[x] ^ top[y]){ if(dep[top[x]] < dep[top[y]]) swap(x, y); x = fa[top[x]];} return dep[x] < dep[y] ? x : y; } int c[N]; void Add(int x, int v){ for(;x<=n;x+=x&-x) c[x] += v;} void modify(int u, int v){ Add(in[u], v); if(ed[u] < n) Add(ed[u] + 1, -v); } int ask(int x){ int ans = 0; for(;x;x-=x&-x) ans += c[x]; return ans;} int query(int u, int v){ return ask(in[u]) + ask(in[v]) - 2 * ask(in[lca(u, v)]); }}B;void Solve(int u, int fa){ int pre = 0; if(u > 1) pre = B.query(u, fa); for(int i = A.first[u]; i; i = A.nxt[i]){ int t = A.to[i]; if(t == fa) continue; Solve(t, u); } for(int i = 0; i < v[u].size(); i++){ int t = v[u][i]; if(t > 0) B.modify(t, 1); else B.modify(-t, -2); } if(u == 1) return; ans[A.idx[u]] = B.query(u, fa) - pre;}int main(){ n = read(); for(int i = 1; i < n; i++){ int x = read(), y = read(); A.add(x, y, i); A.add(y, x, i); } A.dep[1] = 1; A.dfs(1, 0); A.dfs2(1, 1); for(int i = 1; i < n; i++){ int x = read(), y = read(); B.add(x, y); B.add(y, x); } B.dep[1] = 1; B.dfs(1, 0); B.dfs2(1, 1); Solve(1, 0); for(int i = 1; i < n; i++) cout << ans[i] << " "; return 0;}

#include#define cs constusing namespace std;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; } while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f;}cs int N = 2e5 + 5;cs int inf = 1e9 + 7;#define pb push_backint n, m, q, du[N];vector v[N], rev[N];vector s[N];void add(int x, int y){ v[x].pb(y); ++du[x]; rev[y].pb(x); }int f[N];int fa[N][20], sum[N][20];void dp(){ queue q; for(int i = 1; i <= n; i++) if(!du[i]) q.push(i); while(!q.empty()){ int x = q.front(); q.pop(); for(int e = 0; e < v[x].size(); e++){ int t = v[x][e]; f[x] = min(inf, f[x] + f[t] + 1); s[x].push_back(f[x]); } if(v[x].size()){ int ps = 0; for(int e = 1; e < v[x].size(); e++){ if(f[v[x][e]] > f[v[x][ps]]) ps = e; } fa[x][0] = v[x][ps]; sum[x][0] = 1; for(int e = 0; e < ps; e++) sum[x][0] += f[v[x][e]] + 1, sum[x][0] = min(sum[x][0], inf); for(int j = 1; j <= 18; j++){ fa[x][j] = fa[fa[x][j-1]][j-1]; if(!fa[x][j]) break; sum[x][j] = sum[x][j - 1] + sum[fa[x][j - 1]][j-1]; sum[x][j] = min(sum[x][j], inf); } } for(int e = 0; e < rev[x].size(); e++){ int t = rev[x][e]; if(--du[t] == 0) q.push(t); } }}int kth(int x, int k){ if(k == 0) return x; for(int i = 18; i >= 0; i--){ if(fa[x][i] && (f[fa[x][i]] + sum[x][i] >= k) && sum[x][i] <= k) return kth(fa[x][i], k - sum[x][i]); } int nx = lower_bound(s[x].begin(), s[x].end(), k) - s[x].begin(); if(nx) k -= s[x][nx - 1]; return kth(v[x][nx], k - 1);}int main(){ n = read(), m = read(); for(int i = 1; i <= m; i++){ int x = read(), y = read(); add(x, y); } dp(); q = read(); while(q--){ int x = read(), k = read(); if(f[x] < k) puts("-1"); else cout << kth(x, k) << '\n'; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。