• 其实就是一道近乎模板的树上分治题。
• 你们只要想想对于“减去路径上最大点权值”这一点就行了，其它和模板题（POJ-1741）几乎一样。

可以看看我的博客
(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);
}