题解

本题使用BFS + 离线处理 + 差分求解动态图最短路问题。

算法思路：

1. 问题转化：

   • 初始时所有边都可用，随着时间推移某些边会被删除
   • 查询：每个时刻有多少个点能够到达节点 $1$
   • 将删除边的操作倒序处理，变成添加边的操作

2. 边的时效性：

   • 每条边都有一个"失效时间" late[i]
   • 边 $(u, v)$ 在时刻 $t$ 之前都可用，$t$ 之后被删除
   • 初始化所有边的失效时间为 $q+1$（永不失效）
   • 根据查询序列 $p[i]$，设置对应边的失效时间为 $i$

3. BFS求最短路：

   • 从节点 $1$ 开始 BFS
   • 维护 d[v]：节点 $v$ 到节点 $1$ 的最短距离
   • 维护 late[v]：节点 $v$ 的"最晚可达时间"
   • 转移条件：
     • 如果 $d[v] > d[u] + 1$，更新 $d[v]$ 和 $late[v]$
     • 如果 $d[v] = d[u] + 1$，更新 $late[v] = \max(late[v], \min(edge.late, late[u]))$

4. 最晚可达时间的含义：

   • late[v] 表示节点 $v$ 在时刻 $late[v]$ 之前都能到达节点 $1$
   • 使用最短路上所有边的最小失效时间

5. 统计答案：

   • 对于每个节点 $v$，在 ans[late[v]] 处计数
   • 使用前缀和计算每个时刻的答案：$ans[i] += ans[i-1]$

时间复杂度：$O(n + m + q)$

这是一道倒序思维 + BFS 的经典问题，关键在于将删除操作转化为添加操作。

#include<bits/stdc++.h>
#define LF putchar(10)
#define SP putchar(32)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ui N=1e6+5;
template<typename T>void read(T& x)
{
	x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
	while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void readd(T& arg)
{
	double x=0;char ch=getchar();double f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
	while(ch>47&&ch<58){x=x*10.0+(double)(ch&15),ch=getchar();}ch=getchar();
	double e=0.1;while(ch>47&&ch<58){x=x+(ch&15)*e,ch=getchar(),e/=10.0;}arg=x*f;
}
template<typename T,typename... Args>void readd(T& x,Args&... args){readd(x);readd(args...);}
bool check_readc_char(char ch){return (ch>64&&ch<91)||(ch>96&&ch<123);}
template<typename T>void reads(T& x)
{
	char ch=getchar();ui len=0;while(!check_readc_char(ch))ch=getchar();
	while(check_readc_char(ch))x[++len]=ch,ch=getchar();x[len+1]=0;
}
template<typename T,typename... Args>void reads(T& x,Args&... args){reads(x);reads(args...);}
template<typename T>void write(T x){if(x<0){putchar(45);x=-x;}if(x>9)write(x/10);putchar(x%10|48);}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP;write(args...);}}
struct Edge{int to,nxt,late;}edge[N<<1];
int n,m,q,x[N],y[N],head[N],idx,p[N],ans[N],d[N],Q[N],F=1,R,late[N];
bool vis[N];
void add(int u,int v){edge[++idx].to=v,edge[idx].nxt=head[u],edge[idx].late=q+1,head[u]=idx;}
void bfs()
{
	memset(d,0x3f,sizeof d);
	Q[++R]=1,d[1]=0,vis[1]=true;
	while(F<=R)
	{
		int u=Q[F++];
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int v=edge[i].to;
			if(d[v]>d[u]+1)
				d[v]=d[u]+1,Q[++R]=v;
			if(d[v]==d[u]+1&&(!vis[v]||late[v]<min(edge[i].late,late[u])))
				late[v]=min(edge[i].late,late[u]),vis[v]=true;
		}
	}
}
void solve()
{
	read(n,m,q);
	for(int i=1;i<=n;i++)
		late[i]=q+1;
	for(int i=1;i<=m;i++)
	{
		read(x[i],y[i]);
		add(x[i],y[i]);
		add(y[i],x[i]);
	}
	for(int i=1;i<=q;i++)
	{
		read(p[i]);
		edge[(p[i]<<1)-1].late=edge[p[i]<<1].late=i;
	}
	bfs();
	for(int i=1;i<=n;i++)
		ans[late[i]]++;
	for(int i=1;i<=q;i++)
		ans[i]+=ans[i-1];
	for(int i=1;i<=q;i++)
	{
		write(ans[i]);
		LF;
	}
}
int main()
{
//	freopen("wjts.in","r",stdin);
//	freopen("wjts.out","w",stdout);
	int T=1;
//	read(T);
	while(T--)
		solve();
	return 0;
}