NOIP 2016 提高組 Day 1 第二題 天天愛跑步

瘋狂的函數 2022-01-07 20:35:45 阅读数:922

noip 提高 day 第二 天天

題目描述

小C同學認為跑步非常有趣,於是决定制作一款叫做《天天愛跑步》的遊戲。《天天愛跑步》是一個養成類遊戲,需要玩家每天按時上線,完成打卡任務。

這個遊戲的地圖可以看作一棵包含n個結點和n - 1條邊的樹,每條邊連接兩個結點,且任意兩個結點存在一條路徑互相可達。樹上結點編號為從1到n的連續正整數。

現在有m個玩家,第i個玩家的起點為Si,終點為Ti。每天打卡任務開始時,所有玩家 在第0秒 同時從 自己的起點 出發,以 每秒跑一條邊 的速度,不間斷地沿著最短路徑向著 自己的終點 跑去,跑到終點後該玩家就算完成了打卡任務。(由於地圖是一棵樹,所以每個人的路徑是唯一的)

小C想知道遊戲的活躍度,所以在每個結點上都放置了一個觀察員。在結點j的觀察員會選擇在第Wj秒觀察玩家,一個玩家能被這個觀察員觀察到當且僅當該玩家在第Wj秒也 正好 到達了結點j。小C想知道每個觀察員會觀察到多少人?

注意: 我們認為一個玩家到達自己的終點後該玩家就會結束遊戲,他不能等待一段時間後再被觀察員觀察到。即對於把結點j作為終點的玩家:若他在第Wj秒前到達 終點,則在結點j的觀察員 不能觀察到 該玩家;若他 正好 在第Wj秒到達終點,則在結點j的觀察員 可以觀察到 這個玩家。

輸入

第一行有兩個整數n和m。其中n代錶樹的結點數量,同時也是觀察員的數量, m代錶玩家的數量。

接下來n - 1行每行兩個整數u和v,錶示結點u到結點v有一條邊。

接下來一行n個整數,其中第j個整數為Wj,錶示結點j出現觀察員的時間。 接下來m行,每行兩個整數Si和Ti,錶示一個玩家的起點和終點。

對於所有的數據,保證1 <= Si, Ti <= n,0 <= Wj <= n。

輸出

輸出1行n個整數,第j個整數錶示結點j的觀察員可以觀察到多少人。

樣例輸入

6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6

樣例輸出

2 0 0 1 1 1

提示

【樣例1說明】

對於1號點,W1=0,故只有起點為1號點的玩家才會被觀察到,所以玩家1和玩家2被觀察到,共2人被觀察到。

對於2號點,沒有玩家在第2秒時在此結點,共0人被觀察到。

對於3號點,沒有玩家在第5秒時在此結點,共0人被觀察到。

對於4號點,玩家1被觀察到,共1人被觀察到。

對於5號點,玩家2被觀察到,共1人被觀察到。

對於6號點,玩家3被觀察到,共1人被觀察到。

每個測試點時限2秒。

【子任務】

每個測試點的數據規模及特點如下錶所示。提示:數據範圍的個比特上的數字可以幫助判斷是哪一種數據類型。

程序實現

#include<bits/stdc++.h>
using namespace std;
const int SIZE=300000;
int n,m,tot,h[SIZE],deep[SIZE],fa[SIZE][20],w[SIZE];
struct edge
{
int to,next;
};
edge E[SIZE*2],e1[SIZE*2],e2[SIZE*2];
void add(int x,int y)
{
E[++tot].to=y;
E[tot].next=h[x];
h[x]=tot;
}
int tot1,tot2,h1[SIZE],h2[SIZE];
void add1(int x,int y)
{
e1[++tot1].to=y;
e1[tot1].next=h1[x];
h1[x]=tot1;
}
void add2(int x,int y)
{
e2[++tot2].to=y;
e2[tot2].next=h2[x];
h2[x]=tot2;
}
void dfs1(int x)
{
for(int i=1;(1<<i)<=deep[x];i++)
{
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for(int i=h[x];i;i=E[i].next)
{
int y=E[i].to;
if(y==fa[x][0])
{
continue;
}
fa[y][0]=x;
deep[y]=deep[x]+1;
dfs1(y);
}
}
int get_lca(int x,int y)
{
if(x==y)
{
return x;
}
if(deep[x]<deep[y])
{
swap(x,y);
}
int t=log(deep[x]-deep[y])/log(2);
for(int i=t;i>=0;i--)
{
if(deep[fa[x][i]]>=deep[y])
{
x=fa[x][i];
}
if(x==y)
{
return x;
}
}
t=log(deep[x])/log(2);
for(int i=t;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int b1[SIZE*2],b2[SIZE*2],js[SIZE],dist[SIZE],s[SIZE],t[SIZE],l[SIZE],ans[SIZE];
void dfs2(int x)
{
int t1=b1[w[x]+deep[x]], t2=b2[w[x]-deep[x]+SIZE];
for(int i=h[x];i;i=E[i].next)
{
int y=E[i].to;
if(y==fa[x][0])
{
continue;
}
dfs2(y);
}
b1[deep[x]]+=js[x];
for(int i=h1[x];i;i=e1[i].next)
{
int y=e1[i].to;
b2[dist[y]-deep[t[y]]+SIZE]++;
}
ans[x]+=b1[w[x]+deep[x]]-t1+b2[w[x]-deep[x]+SIZE]-t2;
for(int i=h2[x];i;i=e2[i].next)
{
int y=e2[i].to;
b1[deep[s[y]]]--;
b2[dist[y]-deep[t[y]]+SIZE]--;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
deep[1]=1;
fa[1][0]=1;
dfs1(1);
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]);
int lca=get_lca(s[i],t[i]);
dist[i]=deep[s[i]]+deep[t[i]]-2*deep[lca];
js[s[i]]++;
add1(t[i],i);
add2(lca,i);
if(deep[lca]+w[lca]==deep[s[i]])
{
ans[lca]--;
}
}
dfs2(1);
for(int i=1; i<=n; i++)
{
printf("%d ", ans[i]);
}
return 0;
}
版权声明:本文为[瘋狂的函數]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201072035449614.html