987445426yu @ 2017-06-18 11:42:18
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=310000;
int EdgeCnt,n,m;
struct Edge{
int j,next;
}e[maxn];
int w[maxn],a[maxn],s[maxn],t[maxn],ans[maxn];
bool add,vis[maxn];
void addedge(int u,int v){
int p=++EdgeCnt;
e[p].j=v;e[p].next=a[u];a[u]=p;
// printf("u=%d a[u]=%d\n",u,a[u]);
}
void dfs1(int s,int t,int time){
if (vis[s])return;
// printf("s=%d t=%d time=%d add=%d w[s]=%d\n",s,t,time,add,w[s]);
if (s==t){
if (w[s]==time)ans[s]++;
add=true;return;
}
vis[s]=true;
int p=a[s];
//printf("s=%d p=%d \n",s,a[s]);
while (p){
//printf("%d %d \n",p,e[p].j);
dfs1(e[p].j,t,time+1);
p=e[p].next;
}
if (add && w[s]==time)ans[s]++;
}
int main(){
//freopen("running.in","r",stdin);
//freopen("running.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);addedge(v,u);
}
for (int i=1;i<=n;i++)
scanf("%d",&w[i]);
for (int i=1;i<=m;i++)
scanf("%d%d",&s[i],&t[i]);
if (n<1000){
for (int i=1;i<=m;i++){
memset(vis,0,sizeof(vis));add=false;
dfs1(s[i],t[i],0);
//printf("\n\n\n\n");
}
for (int i=1;i<=n;i++)
printf("%d ",ans[i]);
}
return 0;
}
by KEIONG @ 2017-08-09 11:02:01
你这样搜索 的正确性是严格的吗 其实我一直没有懂 是最短路径唯一 还是路径唯一
by 52dyd @ 2017-08-22 11:41:38