XP04 - day07

集团-陈超杰

2026-08-18 20:49:33

发布于：广东

114阅读

0回复

0点赞

考试题解

STA-station

#include<bits/stdc++.h>
using namespace std;
vector<int> tr[1000010];
long long dp[1000010];
int size[1000010];
long long ans = 0,id =0;
int n;
void dfs(int u,int fa){
    size[u] = 1;
    for(int son:tr[u]){
        if(son==fa)continue;
        dfs(son,u);
        dp[u]+=dp[son]+size[son];//深度之和
        size[u]+=size[son];//子树的结点数量
    }
}
void dfs1(int u,int fa){
    for(int son:tr[u]){
        if(son==fa)continue;
        dp[son]+=(dp[u]-dp[son])+size[u]-2*size[son];
        size[son]=n;
        if(ans<dp[son]){
            ans=dp[son];
            id = son;
        }
        dfs1(son,u);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n-1;i++){
        int a,b;
        cin>>a>>b;
        tr[a].push_back(b);
        tr[b].push_back(a);
    }
    dfs(1,0);
    ans = dp[1];
    id = 1;
    dfs1(1,0);
    cout<<id;
    return 0;
}

两次DFS 求树的直径边权>=0

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
vector<int> e[N];
int dep[N];

int maxx=1;
void dfs(int u,int fa){
    if(dep[maxx]<dep[u]){
        maxx=u;
    }
    for(int v:e[u]){
        if(v==fa) continue;
        dep[v]=dep[u]+1;
        dfs(v,u);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dep[1]=0;
    dfs(1,0);
    int yuan=maxx;
    maxx=yuan;
    dep[yuan]=0;
    dfs(yuan,0);
    cout<<dep[maxx];
}

树上游戏 (hard)

#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

vector<int> tr[N];

// dp[u] 表示：当 u 作为当前根时，
// u 相邻的方向中，有多少个方向是“必输状态”
// 如果 dp[u] > 0，说明 u 可以走到一个必输状态，因此 u 必胜
// 如果 dp[u] == 0，说明 u 无论往哪里走，对方都不是必输，因此 u 必输
int dp[N];


// 第一次 DFS：先以 1 为根，求“只看子树”的状态
void dfs(int u,int fa){

    dp[u] = 0;

    for(int son:tr[u]){
        if(son==fa) continue;

        dfs(son,u);

        // 如果 son 是必输状态
        // 那么 u 可以走到 son
        // 所以对 u 来说，多了一个可以走向必输状态的方向
        if(dp[son]==0){
            dp[u]++;
        }
    }
}


// 第二次 DFS：换根
// 第一次 DFS 只统计了“儿子方向”
// 但对于每个点来说，父亲方向也应该算进去
void dfs_re(int u,int fa){

    for(int son:tr[u]){
        if(son==fa) continue;

        // dp[u] 里面包含了 son 对 u 的贡献
        // 如果 son 本身是必输状态，那么它给 u 贡献了 1
        // 换根到 son 时，要先把 son 这个方向删掉
        int now = dp[u] - (dp[son]==0 ? 1 : 0);

        // now 表示：
        // 如果站在 u，且不能往 son 方向走，
        // 那么 u 是否为必输状态
        //
        // now == 0：
        // 说明 u 除了 son 以外，没有任何必输方向
        // 那么从 son 看向 u 时，u 就是一个必输状态
        //
        // 所以 son 多了一个“父亲方向的必输状态”
        if(now==0){
            dp[son]++;
        }

        dfs_re(son,u);
    }
}

int main() {
    int n,t;
    cin>>n>>t;

    for(int i=1;i<=n-1;i++){
        int a,b;
        cin>>a>>b;

        tr[a].push_back(b);
        tr[b].push_back(a);
    }

    // 第一次 DFS：
    // 先固定 1 为根，只考虑向儿子走的情况
    dfs(1,-1);

    // 第二次 DFS：
    // 把父亲方向的影响补进去
    // 最终 dp[u] 就表示 u 作为起点时的完整状态
    dfs_re(1,-1);

    while(t--){
        int k;
        cin>>k;

        // dp[k] > 0：
        // 存在一个相邻方向是必输状态
        // 当前玩家走过去后，可以让对手进入必输状态
        // 所以当前点是必胜
        if(dp[k]){
            cout<<"zzk"<<endl;
        }else{
            // 一个必输方向都没有
            // 所以当前点是必输
            cout<<"kht"<<endl;
        }
    }

    return 0;
}

树上游戏

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
vector<int> tr[N];
int dp[N];
void dfs(int u,int fa){
    dp[u] = 0;//必输
    for(int son:tr[u]){
        if(son==fa)continue;
        dfs(son,u);
        if(dp[son]==0)dp[u] = 1;
    }
}
int main() {
    int n,t;
    cin>>n>>t;
    for(int i=1;i<=n-1;i++){
        int a,b;
        cin>>a>>b;
        tr[a].push_back(b);
        tr[b].push_back(a);
    }
    int k;
    cin>>k;
    dfs(k,-1);
    if(dp[k])cout<<"zzk";
    else cout<<"kht";
    return 0;
}

树上慈善基金

#include <bits/stdc++.h>
using namespace std;

const int N = 6010;
int n;
vector<int> tr[N];
long long dp[N][2],a[N];
void dfs(int u,int fa){
    dp[u][1] = a[u];//偷
    dp[u][0] = 0;//不偷
    for(int son:tr[u]){
        if(son==fa)continue;
        dfs(son,u);//自下而上
        dp[u][0] += max(dp[son][0],dp[son][1]);
        dp[u][1] += dp[son][0];
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin>>a[i];
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        tr[a].push_back(b);
        tr[b].push_back(a);
    }
    dfs(1, -1);
    cout<<max(dp[1][0],dp[1][1]);
    return 0;
}

树的直径

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, ans;
vector<int> g[N];
int dfs(int u, int father) {
    int d1 = 0, d2 = 0; // 最大和次大
    for (int v : g[u]) {
        if (v == father) continue;
        int d = dfs(v, u) + 1; // 边权就是 1
        if (d > d1) {
            d2 = d1;
            d1 = d;
        } else if (d > d2) {
            d2 = d;
        }
    }
    ans = max(ans, d1 + d2);
    return d1;
}
int main() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, -1);
    cout << ans << endl;
    return 0;
}

树上差分

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010,M = 20;
vector<int> tr[N];
int fa[N][M]; // 往上跳 2^j 次后的点是谁
long long dep[N],a[N],ans = 0;
void dfs(int u,int p){
    fa[u][0] = p;
    // 在递归儿子之前，先把 u 的祖先表算好
    for(int i=1;i<=M-1;i++){
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for(int son:tr[u]){
        if(son == p) continue;
        dep[son] = dep[u] + 1;
        dfs(son, u);
    }
}
// 先将 x 和 y 逼近到同一深度
int lca(int x,int y){
    if(dep[x] < dep[y]) swap(x,y); // 让 x 更深
    // 提升 x
    for(int i=M-1;i>=0;i--){
        if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    }
    if(x == y) return x;
    // 同时跳
    for(int i=M-1;i>=0;i--){
        if(fa[x][i] != fa[y][i]){
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

void dfs1(int u,int p){
    for(int son:tr[u]){
        if(son==p)continue;
        dfs1(son,u);
        a[u]+=a[son];//自下而上
    }
    ans=max(ans,a[u]);
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        tr[a].push_back(b);
        tr[b].push_back(a);
    }
    dep[1] = 1;
    dfs(1, 0);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        int p = lca(x,y);
        a[x]++;
        a[y]++;
        a[p]--;
        a[fa[p][0]]--;
    }
    dfs1(1,0);
    cout<<ans;
    return 0;
}

自上而下子树批量修改【模版题】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
int n,m;
ll tag[N],ans[N];
vector<int> g[N];
void dfs(int u,int fa){
    ans[u]=ans[fa]+tag[u];
    for(int v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // 所有修改先记录在对应根节点上
    while(m--){
        int x;
        ll v;
        cin>>x>>v;
        tag[x]+=v;
    }
    // 从根节点1往下累加
    dfs(1,0);
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}

DFS序

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=5e5+10;
int n,m;
int dfn[N],out[N],id[N],cnt;
ll b[N],ans[N];
vector<int> g[N];
void dfs(int u,int fa){
    dfn[u]=++cnt;
    id[cnt]=u;
    for(int v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
    out[u]=cnt;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    while(m--){
        int x;
        ll v;
        cin>>x>>v;
        // 子树x -> DFS序区间 [dfn[x],out[x]]
        b[dfn[x]]+=v;
        b[out[x]+1]-=v;
    }
    // 差分还原
    for(int i=1;i<=n;i++){
        b[i]+=b[i-1];
        // DFS序第i个位置对应节点id[i]
        ans[id[i]]=b[i];
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}

LCA最近公共祖先朴素版

LCA最近公共祖先倍增优化

树的属性

有帮助，赞一个

去预览

0/2000

全部评论 2

gaojiarui是給

#include <iostream>
#include <vector>
using namespace std;
constexpr int N = 4e4 + 10;
class node {
public:
	int to, w;
};
vector<node> tr[N];
int deep[N], fa[N][25];
long long dist[N];
int n, m;
void dfs(int u, int p) {
	fa[u][0] = p;
	for (int i = 1; i < 20; i++) {
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	}
	for (auto e : tr[u]) {
		int v = e.to, w = e.w;
		if (v == p) {
			continue;
		}
		deep[v] = deep[u] + 1;
		dist[v] = dist[u] + w;
		dfs(v, u);
	}
}
int lca(int u, int v) {
	if (deep[u] < deep[v]) {
		swap(u, v);
	}
	int diff = deep[u] - deep[v];
	for (int i = 0; i < 20; i++) {
		if (diff & (1 << i)) {
			u = fa[u][i];
		}
	}
	if (u == v) {
		return u;
	}
	for (int i = 20 - 1; i >= 0; i--) {
		if (fa[u][i] != fa[v][i]) {
			u = fa[u][i];
			v = fa[v][i];
		}
	}
	return fa[u][0];
}
void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		tr[i].clear();
	}
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		tr[u].push_back({ v, w });
		tr[v].push_back({ u, w });
	}
	deep[1] = 1;
	dist[1] = 0;
	dfs(1, 0);
	while (m--) {
		int u, v;
		cin >> u >> v;
		int p = lca(u, v);
		cout << dist[u] + dist[v] - 2 * dist[p] << '\n';
	}
	cout << '\n';
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}