社区讨论

求助大佬,为什么此题要建立双向边

AT_abc138_d [ABC138D] Ki参与者 6已保存回复 10

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@lo3781p6
此快照首次捕获于
2023/10/24 01:55
2 年前
此快照最后确认于
2023/10/24 01:55
2 年前
查看原帖

这是我用边表只建单向边的代码,在atcoder上大部分数据都过了,赛后的hack数据没过:

CPP
#include<bits/stdc++.h>
using namespace std;
const int Maxn=2*1e5;
int n,q,t,v;
int to[Maxn<<1],head[Maxn<<1],net[Maxn],tot;
int pre[Maxn+10],val[Maxn];
int a,b;
void add(int u,int v)
{
	to[++tot]=v;
	net[tot]=head[u];
	head[u]=tot;
}
void dfs(int now)
{
	for(int i=head[now];i;i=net[i])
	{
		pre[to[i]]=val[to[i]]+pre[now];
		dfs(to[i]);		
	}
}
int main()
{
	cin>>n>>q;
	for(int i=1;i<n;i++)
	{
		cin>>a>>b;
		add(a,b);
	}
	for(int i=1;i<=q;i++)
	{
		cin>>t>>v;
		val[t]+=v;
	}
	pre[1]=val[1];
	dfs(1);
	for(int i=1;i<=n;i++)
		cout<<pre[i]<<" ";
	return 0;
}

这是vector建双向边的代码,ac了:

CPP
#include<bits/stdc++.h>
using namespace std;
const int Maxn=2*1e5;
int n,q,t,v;
vector<int> a[Maxn<<1];
int pre[Maxn+10];
int aa,b;
void dfs(int now,int fa)
{
	pre[now]+=pre[fa];
	for(int i=0;i<a[now].size();i++)
		if(a[now][i]!=fa)
			dfs(a[now][i],now);		
}
int main()
{
	cin>>n>>q;
	for(int i=1;i<n;i++)
	{
		cin>>aa>>b;
		a[aa].push_back(b);
		a[b].push_back(aa);
	}
	for(int i=1;i<=q;i++)
	{
		cin>>t>>v;
		pre[t]+=v;
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
		cout<<pre[i]<<" ";
	return 0;
}

是单向变和双向边的问题

还是边表和vector的问题呢???

求助大佬们

回复

10 条回复,欢迎继续交流。

正在加载回复...