1 条题解
-
0
hehepig LV 5 MOD @ 8 年前
- 其实就是一道近乎模板的树上分治题。
- 你们只要想想对于“减去路径上最大点权值”这一点就行了,其它和模板题(POJ-1741)几乎一样。
可以看看我的博客
(http://blog.csdn.net/jackypigpig/article/details/70227554)
- 1
可以看看我的博客
(http://blog.csdn.net/jackypigpig/article/details/70227554)
#include <cstdio>
#include <algorithm>
#define Mn 100005
#define Mv 10000005
#define add(x,y) (to[++num]=head[x],head[x]=num,edge[num]=y)
#define For(x) for (int h=head[x],o=edge[h]; h; o=edge[h=to[h]])
using namespace std;
int n,p;
int edge[2*Mn+5],to[2*Mn+5],head[2*Mn+5],del[Mn+5],num;
int R,cnt,mins,v[Mn+5],dis[Mn+5],siz[Mn+5],mx[Mn+5],com[Mn+5],bin[Mv+5],daan;
long long ans;
int mo(int x){
int kkk=x%p;
return (kkk<0 ? kkk+p:kkk);
}
void Input(){
scanf("%d%d",&n,&p);
for (int i=1,o1,o2; i<n; i++) scanf("%d%d",&o1,&o2),add(o1,o2),add(o2,o1);
for (int i=0; i<n;) scanf("%d",&v[++i]);
return;
}
int get_siz(int x,int fa){
siz[x]=1;
For (x) if (o!=fa && !del[o]) siz[x]+=get_siz(o,x);
return siz[x];
}
void dfs_R(int x,int tot,int fa){
int mxs=tot-siz[x];
For(x) if (o!=fa && !del[o]){
mxs=max(mxs,siz[o]);
dfs_R(o,tot,x);
}
if (mxs<mins) mins=mxs,R=x;
}
void get_dis(int x,int tot,int lmx,int fa){
dis[++cnt]=tot%=p;//-----------------!!
mx[cnt]=lmx;
For(x) if (!del[o] && o!=fa)
get_dis(o,tot+v[o],max(lmx,v[o]),x);
}
bool cmp(int x,int y){return mx[x]<mx[y];}
int work(int x,int r){
cnt=daan=0;
if (x==r) get_dis(x,v[x],v[x],0);
else get_dis(x,v[x]+v[r],max(v[x],v[r]),r);
for (int i=1; i<=cnt; i++) com[i]=i;
sort(com+1,com+cnt+1,cmp);
for (int i=1,I=com[i]; i<=cnt; I=com[++i]){
//dis[I]+dis[j]-v[r]-mx[I] == 0 (%p)
//dis[j] == v[r]+mx[I]-dis[I]
daan+=bin[mo(mx[I]+v[r]-dis[I])];
bin[dis[I]]++;
}
for (int i=1; i<=cnt; i++) bin[dis[i]]=0;
return daan;
}
void dfs(int x){
cnt=0;
mins=Mn+1;
get_siz(x,0);
dfs_R(x,siz[x],0);
int rr=R;
ans+=work(rr,rr);
del[rr]=1;
For(rr) if (!del[o]){
ans-=work(o,rr);
dfs(o);
}
}
int main(){
Input();
dfs(1);
printf("%lld",ans+n);
}