| 记录编号 |
448709 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[NOIP 2016]天天爱跑步 |
最终得分 |
100 |
| 用户昵称 |
 CSU_Turkey |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.851 s |
| 提交时间 |
2017-09-13 10:55:46 |
内存使用 |
33.50 MiB |
显示代码纯文本
#include<bits/stdc++.h>//看了一上午题解可算看懂了半小时就码完了，理解了还是很好写的，码量不大
#define v e[i].to//大概意思是将每条路径拆成两端，s--lc(s,t),t--lc(s,t)，然后分两次dfs计算
using namespace std;//对于s--lc(s,t)这种，我们发现当dep[i]+w[i]=dep[s]时，以s为起点的路径(前提是还没到终点)经过i
const int ma=300005;//t--lc(s,t)同理，dep[t]-dep[i]=len-w[i],移一下项，dep[i]-w[i]=dep[t]-len
//等式两边分别对应第一个等式两边，以第一个为例(因为他简单一点)对于任意一个点i，
//我们需要找出所有dep[s]=dep[i]+w[i]的s，这种s存在两种，一种是以i为s的，另外一种是在s的子树中并且还没有到达
//终点的(其实可以看成一种，只不过处理的时候有点小细节),我们通过一个数组来记录处理到i点符合条件的s有多少个(差分实现)
//每次处理前加上以i点为起点出发的那些，然后加到ans[i]上去，(这里有可能会把别的树上“符合条件”(因为只是记录深度，所以会把不符合的记录进去)的加上，但事实上是不正确的，
//所以需要在递归该子树之前记录一下当前值，计算完之后减去当前值就是该子树中符合条件的个数)然后再把以i为终点的那些点
//的s所对应位置-1，(vector实现)（这个顺序很重要，因为尽管以i结尾或开始，他们也是可以被i观察到的）,减去的原因是因为这个点已经到
//达了终点，继续往上处理的过程中是不能加这些点的
//另一种情况有可能出现负数，所以要开2倍大小，直接令所有的下标+ma
//两种情况有可能会重复计算lc这个点的贡献，所以最后特判一下去掉那些lc贡献了两次的点
int n,m,fa[ma],dep[ma],son[ma],top[ma],siz[ma],fi[ma],tot;//树剖数组和前向星数组
int w[ma],ans[ma],a1[ma],a2[ma<<1],val[ma];//观察时间，每个点的贡献 ,两种情况的桶 ,以当前点为起点的个数
vector<int>s1[ma],s2[ma],s3[ma];//以当前点为终点的点起点所对应的桶的位置，以当前点为起点的点对应的桶的位置
struct edge{
int to,next;
}e[ma<<1];
void edge_add(int x,int y){
e[++tot].to=y;
e[tot].next=fi[x];
fi[x]=tot;
}
struct path{//记录每条路的出发，终止，以及他们的lca，还有这条路的长度
int s,t,lc,len;
}p[ma];
int read(){
int a=0;
char ch=getchar();
while(!(ch<='9'&&ch>='0'))ch=getchar();
while(ch<='9'&&ch>='0'){
a=(a<<1)+(a<<3)+(ch^'0');
ch=getchar();
}
return a;
}
void init1(int x){
for(int i=fi[x];i;i=e[i].next){
if(dep[v])continue;
dep[v]=dep[x]+1;
fa[v]=x;
init1(v);
siz[x]+=siz[v];
if(siz[v]>siz[son[x]])son[x]=v;
}
}
void init2(int x,int y){
top[x]=y;
if(son[x])init2(son[x],y);
for(int i=fi[x];i;i=e[i].next){
if(top[v])continue;
init2(v,v);
}
}
int get_lc(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
void dfs(int x){
int now=dep[x]+w[x],h=a1[now];
for(int i=fi[x];i;i=e[i].next){
if(v==fa[x])continue;
dfs(v);
}
a1[dep[x]]+=val[x];
ans[x]+=a1[now]-h;
int si=s1[x].size();
for(int i=0;i<si;i++){
a1[dep[s1[x][i]]]--;
}
}
void Dfs(int x){
int now=dep[x]-w[x]+ma,h=a2[now];
for(int i=fi[x];i;i=e[i].next){
if(v==fa[x])continue;
Dfs(v);
}
int si=s2[x].size();
for(int i=0;i<si;i++){
a2[s2[x][i]+ma]++;
}
ans[x]+=a2[now]-h;
si=s3[x].size();
for(int i=0;i<si;i++){
a2[s3[x][i]+ma]--;
}
}
int main()
{
freopen("runninga.in","r",stdin);
freopen("runninga.out","w",stdout);
// freopen("1.txt","r",stdin);
n=read();m=read();
for(int i=1;i<n;i++){
int x,y;
x=read();y=read();
edge_add(x,y);
edge_add(y,x);
}
for(int i=1;i<=n;i++)w[i]=read(),siz[i]=1;
dep[1]=1;init1(1);init2(1,1);
for(int i=1;i<=m;i++){
p[i].s=read();p[i].t=read();
p[i].lc=get_lc(p[i].s,p[i].t);
p[i].len=dep[p[i].s]+dep[p[i].t]-(dep[p[i].lc]<<1);
val[p[i].s]++;
s1[p[i].lc].push_back(p[i].s);
}
dfs(1);
for(int i=1;i<=m;i++){
s2[p[i].t].push_back(dep[p[i].t]-p[i].len);
s3[p[i].lc].push_back(dep[p[i].t]-p[i].len);
}
Dfs(1);
for(int i=1;i<=m;i++){
if(dep[p[i].s]-dep[p[i].lc]==w[p[i].lc])ans[p[i].lc]--;
}
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
return 0;
}