夏令营7.17总结

昨天休息所以没有总结。

数上问题

数的定义和性质

什么是树？

• 有$n-1$条边且连通
• 有$n-1$条边且无环
• 任意两点之间有唯一路径

T1 构图判树

直接找所有的包含区间，找到就加边，如果超过了，就输出no。

条件：数只有$n-1$条变F.

有根数

指定一个顶点r为根节点，就可以解决很多问题。

节点到根节点的深度称为深度，深度相同的节点位于同一层。高度是深度的最大值。

还有一堆：


树上DFS

白点：没访问过

黑点：已经访问但是没有回溯

黑点：已返回且已回溯

dfs时可以使用时间戳。分别标记访问到时和回溯到时。根节点标记为时间0。

T2 数后代

int cnt[N];
vector<pair<int,int>> f[N];
vector<int> g[N];

int ans[N];
void dfs(int x,int fa){
    dep[x]=dep[fa]+1;
    for(auto p:f[x]){
        int di=p.first,i=p.second;
        ans[i]-=cnt[di];
    }
    cnt[dep[x]]++;//放这里！！！！！！！！！！
    for(auto y:g[x]){
        if(y!=g[x]){
            dfs(y,x);
        }
    }
    for(auto p:f[x]){
        int di=p.first,i=p.second;
        ans[i]+=cnt[di];
    }
}

T3 树上炸弹

核心思路就是用只能往下的炸弹模拟既能上又能下的炸弹，再扩展。

也可以dp：

令$f[u][i]$为子树$u$里的炸弹$(p,w)$中，满足$i\le w-d(p,u)$的有多少个。那么：

• 在子树$u$中，能炸到点$u$的炸弹数量就是$f[u][0]$。
• 在子树$a_1$里但不在子树$u$里，能炸到$u$的炸弹数量就是$f[a_1][1]-f[u][2]$。
• 在子树$a_2$里但不在子树$a_1$里，能炸到$u$的炸弹数量就是$f[a_2][2]-f[1_1][3]$。
• ………..

T4 Padel Prize Pursuit

考虑一个有$m-1$个节点的图，点从$0$到$m$编号。每一个点代表了一枚奖牌。也就是一天或一场比赛。若第$i$枚奖牌下一次易主是在第$j$场比赛之后，那么就从$i$向$j$连接一条边。

考虑从根节点向下走到一个点$v$的过程。我们维护一个数组$d[0…n-1]$，当我们走到点$v$时，$d[i]$就是人$i$持有奖牌$v$个晚上。

在维护数组$d$时，顺便维护$d$的argmax（即$d$在哪个下标$i$的位置取得了最大值）。

k祖先问题

给你一个有$n$个点的有根树，点从$1$编号到$n$。回答$q$个询问，询问内容为求点$u$的第$k$个祖先。

这里使用倍增。

const int log=bitwidth(n);
int jump(int u,int k){
    for(int i=0;i<log;i++){
        if(k>>i&1){
            u=anc[u][i];
        }
    }
    return u;
}

CF1175E【非例题】

预处理：

• 把区间按左端点从小到大排序，左端点相同的按照右端点从大到小排序。
• 去除无用的区间
• 找出每个区间的父节点
• 计算出倍增表

对于每个询问$[x,y]$：

• 二分查找最后一个满足左端点小于等于$x$的区间，设此区间的编号为$i$。
• 在$i$所在的有根树上，从节点$i$出发，向上跳到第一个右端点大于等于$y$的区间，计算跳过的距离。

LCA问题

给一棵有根树，回答$t$个问题：求点$u$与点$v$的最近公共祖先。

方法1 使用is_anc函数

有一个函数is_anc(x,y)来判断点$x$是不是点$y$的祖先，那么就可以实现这个问题。

int lca(int u,int v){
    if(is_anc(u,v)) return u;
    if(is_anc(v,u)) return v;
    for(int i=log-1;i>=0;i++){
        if(anc[u][i]&&!is_anc(anc[u][i],v)){
            u=anc[u][i];
        }
    }
    return anc[u][0];
}

方法2 使用节点深度

如果已经求出了每个点$u$的深度$depth[u]$，那么就可以求$u$和$v$的最近公共祖先。

int lca(int u,int v){
    if(depth[u]<depth[v]) swap(u,v);
    u=jump(u,depth[u]-depth[v]);
    if(u==v) return u;
    for(int i=log-1;i>=0;i--){
        if(anc[u][i]!=anc[v][i]){
            u=anc[u][i];
            v=anc[v][i];
        }
    }
    return anc[u][0];
}

T6 【模板】 最近公共祖先

这题用上面两种方法任选其一完成即可。