专栏文章

10.6总结

kkamikuQAQ
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minoailw
此快照首次捕获于
2025/12/02 05:40
3 个月前
此快照最后确认于
2025/12/02 05:40
3 个月前
查看原文

T1

lca板子
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e4+10;
int dp[maxn][21],dep[maxn];
vector<int>g[maxn];
void addline(int u,int v) {
	g[u].push_back(v);
	g[v].push_back(u);
}
void dfs(int u,int fa){
	dp[u][0]=fa;
	dep[u]=dep[fa]+1;
	for(int i=1;i<=20;i++) {
		dp[u][i]=dp[dp[u][i-1]][i-1];
	}
	for(int i=0;i<g[u].size();i++) {
		int v=g[u][i];
		if(v!=fa) {
			dep[v]=dep[u]+1;
			dfs(v,u);
		}
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]) {
		swap(x,y);
	}
	for(int i=20;i>=0;i--) {
		if(dep[dp[x][i]]>=dep[y]) {
			x=dp[x][i];
		}
	}
	if(x==y) {
		return x;
	}
	for(int i=20;i>=0;i--) {
		if(dp[x][i]!=dp[y][i]) {
			x=dp[x][i];
			y=dp[y][i];
		}
	}
	return dp[x][0];
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,rt;
	cin>>n;
	for(int i=1;i<=n;i++) {
		int x,y;
		cin>>x>>y;
		if(y==-1){
			rt=x; 
		} else {
			addline(x,y);
		}
	}
	dep[rt]=1;
	dfs(rt,0);
	int m;
	cin>>m;
	while(m--) {
		int x,y;
		cin>>x>>y;
		if(x==lca(x,y)) {
			cout<<1;
		} else if(y==lca(x,y)) {
			cout<<2;
		} else{
			cout<<0;
		}
		cout<<endl;
	}
	return 0;
}

T2

首先对于树上三个点汇聚在一个点上会有两种情况
2
可以看出，三个点要么有共同的祖先要么可以汇聚在三个点中的一个点
然后我们要求到公共点的距离，由于不知道公共点在哪里，所以我们通过公共点走到其他两个点，画记一遍路线可得走的总距离是公共点到其他三点距离的两倍，即公共点到其他点的距离为 (dis(a,b)+dis(b,c)+dis(a,c))/2(dis(a,b)+dis(b,c)+dis(a,c))/2
然后因为dis(a,b)=dep[a]+dep[b]−2∗dep[a]∗dep[b]dis(a,b)=dep[a]+dep[b]-2*dep[a]*dep[b]得其他点到公共点的距离为dep[a]+dep[b]+dep[c]−dep[lca(a,b)]−dep[lca(b,c)]−dep[lca(a,c)]dep[a]+dep[b]+dep[c]-dep[lca(a,b)]-dep[lca(b,c)]-dep[lca(a,c)] 而上述的值是定值，接下来只需要确定在三个祖先中哪个是最优的就行，这三个点到达lca和另外两个lca不一样的点时候的距离最小
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+7;
vector<int>g[maxn];
void addline(int u,int v) {
	g[u].push_back(v);
	g[v].push_back(u);
}
int dep[maxn],dp[maxn][21];
void dfs(int u,int fa) {
	dep[u]=dep[fa]+1;
	dp[u][0]=fa;
	for(int i=1;i<=20;i++) {
		dp[u][i]=dp[dp[u][i-1]][i-1];
	}
	for(int i=0;i<g[u].size();i++) {
		int v=g[u][i];
		if(v!=fa) {
			dep[v]=dep[u]+1;
			dfs(v,u);
		}
	}
}
int lca(int x,int y){
	if(dep[x]>dep[y]) {
		swap(x,y);
	}
	for(int i=20;i>=0;i--) {
		if(dep[dp[y][i]]>=dep[x]) {
			y=dp[y][i];
		}
	}
	if(x==y) {
		return x;
	}
	for(int i=20;i>=0;i--) {
		if(dp[x][i]!=dp[y][i]) {
			x=dp[x][i];
			y=dp[y][i];
		}
	}
	return dp[x][0];
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<n;i++) {
		int u,v;
		cin>>u>>v;
		addline(u,v);
	}
	dfs(1,0);
	for(int i=1;i<=m;i++) {
		int x,y,z,ans;
		cin>>x>>y>>z;
		int l1=lca(x,y),l2=lca(y,z),l3=lca(z,x);
		if(l1==l2) {
			ans=l3;
		} else if(l2==l3) {
			ans=l1;
		} else if(l1==l3){
			ans=l2;
		}
		cout<<ans<<' '<<dep[x]+dep[y]+dep[z]-dep[l1]-dep[l2]-dep[l3]<<'\n';
	}
	return 0;
}

T3

首先要翻译题面的行为 懒得敲字了自己看图
2
将x作为原来y中包含x的子树的根，原来的根变为它的儿子 而我们不难发现，x儿子的深度是不变的而变的只有z和x的深度
首先如果x就是y的直接儿子说明转换如同没转换一样，可以直接输出f[y]
否则我们可以看见，变化的只有x和z的深度，x深度变小而z的深度变大的数值相同，意味着需要-siz[x]+siz[z]，x的深度变成了dep[y]+1则意味着点权和边权的乘积增加(dep[y]−dep[x]−1)∗v[x](dep[y]-dep[x]-1)*v[x] 所以位移后的f(y′)=f(y)+siz[z]−siz[x]−(dep[y]−dep[x]−1)∗v[x]f(y')=f(y)+siz[z]-siz[x]-(dep[y]-dep[x]-1)*v[x]
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
const int maxn = 5e5+10;
vector<int>g[maxn];
int v[maxn], p[maxn], dep[maxn];
int dp[maxn][22];
int siz[maxn], f[maxn];
void addline(int u,int v) {
	g[u].push_back(v);
	g[v].push_back(u);
}
void dfs(int u,int fa){
	siz[u] = v[u];
    dp[u][0] = fa;
    dep[u] = dep[fa] + 1;
	for(int i=1;i<=20;i++) {
		dp[u][i]=dp[dp[u][i-1]][i-1];
	}
	for(int i=0;i<g[u].size();i++) {
		int v=g[u][i];
		if(v!=fa) {
			dfs(v, u);
            siz[u] += siz[v];
            f[u] += f[v];
		}
	}
	f[u] += (siz[u] - v[u]);
}
int lca(int x,int y){
	for(int i=20;i>=0;i--) {
		if(dep[dp[x][i]]>dep[y]) {
			x=dp[x][i];
		}
	}
	return x;
}
int dist(int x,int y) {
	return dep[x]+dep[y]-2*dep[lca(x,y)];
}
int count(int x,int y) {
	return dist(x,y)*v[x];
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		cin>>v[i];
	}
	for(int i=2;i<=n;i++) {
		cin>>p[i];
		addline(p[i],i);
	}
	dfs(1,0);
	while(q--) {
		int x,y;
		cin>>x>>y;
		if(p[x]==y){
			cout<<f[y]<<'\n';
			continue;
		}
		int z=lca(x,y);
		cout << f[y] - (dep[x] - dep[y] - 1) * v[x] + (siz[z] - siz[x]) << "\n";
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...