CSP-S 模拟 19/10/26

写了一个期望 ， 表示走 步到 的期望
巧妙的发现答案就是
证明：考虑走一步多的贡献，显然 独立，考虑

所以答案是

---

对于 的数据
对于 的数据
好题！考场手动画图，用红笔和黑笔画的，所以以下运 B 的是黑树，运 A 的是红树
于是问题转换为将一条黑边染红，然后再红环上断开一条边染黑，且不形成黑环
发现不形成黑环就是说原来的红边连的是两个不同的连通块
我们考虑将穿过两个连通块的边打一个标记，那么在环上的被标记的边的个数就是答案
而在环上的红边对应到原树就是一条链，单点修改链求和，转成子树修改单点查询
考虑一条边会被哪些打上标记，就是使这条边在它链上的那些红边

考场做法：发现一条红边对一段区间都有贡献，于是树剖+暴力线段树分治，另一端可以用 序维护
复杂度

正解， 一条红边的贡献不是可以差分吗，在 加， 减去它的贡献就可以了，用一个 存一下操作
于是又有几种做法，一个是用 暴力维护可以会被影响的边的集合，启发式合并，合并的时候顺便再另一颗树的 序上维护，复杂度
考虑优化，试试用线段树合并，每个点开一棵线段树维护 序上的修改
注意这波操作有点秀，省去了在另一棵树维护树状数组的过程，而直接在线段树上修改
相当于说维护集合没有用，直接维护集合在令一棵树上映射出来的贡献
每次就是将子树的合并，并加上它的贡献

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

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

考场太懒，不写暴力，没有代码分块，最后沦为暴力都不如的废物

考场太懒，不打对拍

考场太懒，没有肉眼挑错，没有关注空间

考场太傲娇，想了的做法，码了，最后明明有时间检查但太过自信

说一下傻逼错误： 预处理到 20，空间刚刚好开 20
本质上是做题时太过浮躁，啥都不想干，暴力不想写，静态查错不想查，今天暴零真是被死
宁静生慧根！

#include<bits/stdc++.h>
#define cs const
using 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<typename T>
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<int>();}
} using namespace IO;
cs int N = 1e6 + 5;
#define pb push_back
int n, ans[N];
typedef pair<int,int> pi;
#define mk make_pair
vector<int> v[N]; // 差分询问
namespace seg{
int rt[N], node, sum[N * 30], ls[N * 30], rs[N * 30];
stack<int> 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<bits/stdc++.h>
#define cs const
using 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<typename T>
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<int>();}
} using namespace IO;
cs int N = 1e6 + 5;
#define pb push_back
int n, ans[N];
typedef pair<int,int> pi;
#define mk make_pair
vector<int> 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<bits/stdc++.h>
#define cs const
using 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_back
int n, m, q, du[N];
vector<int> v[N], rev[N];
vector<int> 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<int> 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;
}