据说是今年NOIP最难一题了。。。我还记得当时满怀期待心情点开Day1的题发现T2就不会了于是怀疑人生良久。。。
啊好像很多大爷都是用线段树合并写的，我怎么什么数据结构都不会啊呜呜呜。。。
题目大意就不说了QWQ
网上的O(n)说法说得好简略啊，我理解了好久。。。可能是我太弱了QAQ这方面的题做得也少
首先我们可以随手推出某个点i可以观测到一个从x跑到y的玩家的话，肯定有d[i]+w[i]=d[x]或者d[i]-w[i]=d[y]-dis【dis为x到y的距离
所以肯定要先求LCA辣，自从转了C++，写tarjan lca只要3行，比pascal的tarjan高到不知道哪里去了，还比倍增快OWO
O(n)的做法比较繁琐。我们需要开一个i点向下能到达的起点的桶cntq[i]和一个i点向下能到达的终点的桶cntz[i]。dfs搜到某个点的时候，cntq[d[x]]+=cnt[x]【cnt[x]表示这个点是起点的个数】，然后对于这个点上的每一个终点cntz[d[y]-dis]++。这样的话某个点i的答案ans[i]=cntq[d[i]+w[i]]+cntz[d[i]-w[i]]。
当起点和终点的lca出栈的时候，要把跟这两个点有关cnts和cntx减掉，因为它们对答案不再有贡献。
但是我们会发现，对于某个点i，其他子树的起点x或终点y【lca(x,y)还未退栈】有可能会被误算贡献【因为开的桶的下标是深度】，所以我们在进入某棵子树之前，先把答案ans[i]计算一次，回溯之后再计算一次答案ans[i]，两个答案相减就是这棵子树的答案了。
还要注意如果i是lca(x,y)的话答案会算重复，需要减掉一个。。。
然后这题就又写完辣【BZOJ上要求的格式太坑了。。。PE了好多次QAQ
代码如下：
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; const int maxn=300010; struct poi{int too,pre,pos;}e[maxn*2],e3[maxn*2],e4[maxn*2],e5[maxn*2],lik[maxn*2]; int n,m,tot1,tot2,tot3,tot4,tot5,ans[maxn],fa[maxn],cntq[maxn*2],cntz[maxn*2],d[maxn],w[maxn],cnt[maxn]; int x,y,tim,elast[maxn*2],llast[maxn*2],e3last[maxn*2],e4last[maxn*2],e5last[maxn*2],q[maxn*2][4]; bool v[maxn]; int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);} void add1(int x,int y){e[++tot1].too=y;e[tot1].pre=elast[x];elast[x]=tot1;} void add2(int x,int y,int z){lik[++tot2].too=y;lik[tot2].pos=z;lik[tot2].pre=llast[x];llast[x]=tot2;} void add3(int x,int y){e3[++tot3].too=y;e3[tot3].pre=e3last[x];e3last[x]=tot3;} void add4(int x,int y){e4[++tot4].too=y;e4[tot4].pre=e4last[x];e4last[x]=tot4;} void add5(int x,int y){e5[++tot5].too=y;e5[tot5].pre=e5last[x];e5last[x]=tot5;} void tarjan(int x) { fa[x]=x;v[x]=1; for(int i=llast[x];i;i=lik[i].pre)if(v[lik[i].too])q[lik[i].pos][3]=gf(lik[i].too); for(int i=elast[x],too=e[i].too;i;i=e[i].pre,too=e[i].too)if(!v[too])d[too]=d[x]+1,tarjan(too),fa[too]=x; } void dfs(int x,int fa) { int lx=cntq[d[x]+w[x]],ly=cntz[d[x]-w[x]+maxn];cntq[d[x]]+=cnt[x]; for(int i=e3last[x];i;i=e3[i].pre)cntz[e3[i].too]++; for(int i=elast[x];i;i=e[i].pre){if(e[i].too!=fa)dfs(e[i].too,x);} ans[x]=cntq[d[x]+w[x]]+cntz[d[x]-w[x]+maxn]-lx-ly; for(int i=e4last[x];i;i=e4[i].pre){cntq[e4[i].too]--;if(e4[i].too==d[x]+w[x])ans[x]--;} for(int i=e5last[x];i;i=e5[i].pre)cntz[e5[i].too]--; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<n;i++)scanf("%d%d",&x,&y),add1(x,y),add1(y,x); for(int i=1;i<=n;i++)scanf("%d",&w[i]); for(int i=1;i<=m;i++)scanf("%d%d",&x,&y),q[i][1]=x,q[i][2]=y,add2(x,y,i),add2(y,x,i),cnt[x]++; tarjan(1); for(int i=1;i<=m;i++) { int dis=d[q[i][1]]+d[q[i][2]]-2*d[q[i][3]]; add3(q[i][2],d[q[i][2]]-dis+maxn); add4(q[i][3],d[q[i][1]]); add5(q[i][3],d[q[i][2]]-dis+maxn); } dfs(1,0); for(int i=1;i<n;i++)printf("%d ",ans[i]); printf("%d",ans[n]); }