记录编号 | 448709 | 评测结果 | AAAAAAAAAAAAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [NOIP 2016]天天爱跑步 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | 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; }