思路：1741的A1送 1.

#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #define Maxn 40010 #define Maxm 80010 #define inf 0x7fffffff using namespace std; int head[Maxn],vi[Maxn],e,ans,num,k,n,m; int mx[Maxn],mi,dis[Maxn],root,size[Maxn]; struct Edge{int u,v,val,next; }edge[Maxm]; void init() {memset(vi,0,sizeof(vi));memset(head,-1,sizeof(head));memset(mx,0,sizeof(mx));memset(dis,0,sizeof(dis));e=ans=0; } void add(int u,int v,int val) {edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].next=head[u],head[u]=e++;edge[e].u=v,edge[e].v=u,edge[e].val=val,edge[e].next=head[v],head[v]=e++; } void dfssize(int u,int fa) {int i,v;size[u]=1;mx[u]=0;for(i=head[u];i!=-1;i=edge[i].next){v=edge[i].v;if(v!=fa&&!vi[v]){dfssize(v,u);size[u]+=size[v];if(size[v]>mx[u]) mx[u]=size[v];}} } void dfsroot(int r,int u,int fa) {int v,i;if(size[r]-size[u]>mx[u]) mx[u]=size[r]-size[u];if(mx[u]<mi) mi=mx[u],root=u;for(i=head[u];i!=-1;i=edge[i].next){v=edge[i].v;if(v!=fa&&!vi[v]){dfsroot(r,v,u);}} } void dfsdis(int u,int d,int fa) {int i,v;dis[++num]=d;for(i=head[u];i!=-1;i=edge[i].next){v=edge[i].v;if(v!=fa&&!vi[v]){dfsdis(v,d+edge[i].val,u);}} } int calc(int u,int d) {int i,j,ret=0;num=0;dfsdis(u,d,0);sort(dis+1,dis+1+num);i=1;j=num;while(i<j)//單調(diào)求點對 {while(dis[i]+dis[j]>k&&i<j)j--;ret+=j-i;i++;}return ret; } void dfs(int u) {int i,v;mi=n;dfssize(u,0);dfsroot(u,u,0);ans+=calc(root,0);vi[root]=1;for(i=head[root];i!=-1;i=edge[i].next){v=edge[i].v;if(!vi[v]){ans-=calc(v,edge[i].val);dfs(v);}} } int main() {int i,j,u,v,val;char cc;while(scanf("%d%d",&n,&m)!=EOF){init();for(i=1;i<=m;i++){scanf("%d%d%d %c",&u,&v,&val,&cc);add(u,v,val);}scanf("%d",&k);dfs(1);printf("%d\n",ans);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/wangfang20/p/3258461.html

總結(jié)

以上是生活随笔為你收集整理的poj 1987 树的分治的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。