5 41 2 31 3 11 4 23 5 10 0Sample Output8(說起來這應該是人生第一道點分治唄。。。quq蒟蒻的悲哀:)題意:給定一棵N(1<= N <=10000)個結點的帶權樹,定義dist(u,v)為u,v兩點間的最短路徑長度,路徑的長度定義為路徑上所有邊的權和。再給定一個 K ,如果對于不同的兩個結點a,b,如果滿足dist(a,b) <=K,則稱(a,b)為合法點對。求合法點對個數。題解:也是剛剛搞完點分治唄。。。%XZK難得一次編譯過AC。。。所謂點分治嘞,就是在一個無根樹里選取一個點作為根【重心】然后再遞歸處理每個子樹對于這道題嘛,我們考慮一條路徑只有兩種情況——經過根or不過根【也可以說是:兩點在同一棵子樹內or不在同一顆子樹內】那么我們就可以得出一個大致框架:記錄每個子樹內的到子樹【我們遞歸處理的樹】根節點距離值,然后從小到大排一個序,就可以計算出符合dist(a,b)<=k的點對個數,用這種方法對每一個子樹計一個res表示合法點對數這個時候要注意:對于一棵這樣的樹 ,由于遞歸的緣故,會有重復計算的情況所以我們的結果ans=ans-sigama res的【即:所有滿足合法的點對-在同一個子樹的點對數】以下是AC代碼:=v=#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define inf 0x7fffffff#define maxn 10010using namespace std;struct node{ int v,w,nxt;}e[maxn*4];int n,k;int vis[maxn];int dis[maxn],dep[maxn];int size[maxn],f[maxn];int head[maxn],cnt;int rt,cd;void add(int u,int v,int w){ e[++cnt].v=v; e[cnt].w=w; e[cnt].nxt=head[u]; head[u]=cnt;}void getroot(int x,int fa,int sum){ size[x]=1;f[x]=0; for(int i=head[x];i!=-1;i=e[i].nxt){ int v=e[i].v; if(!vis[v] && v!=fa){ getroot(v,x,sum); size[x]+=size[v]; f[x]=max(f[x],size[v]); } } f[x]=max(f[x],sum-size[x]); if(f[x]<f[rt])rt=x; }void getdeep(int x,int fa){ dis[++cd]=dep[x]; for(int i=head[x];i!=-1;i=e[i].nxt){ int v=e[i].v; if(!vis[v] && v!=fa){ dep[v]=dep[x]+e[i].w; getdeep(v,x); } }}int work(int x,int val){ dep[x]=val;cd=0; getdeep(x,0); sort(dis+1,dis+cd+1); int res=0,l=1,r=cd; while(l<r){ if(dis[l]+dis[r]<=k)res+=r-l,l++; else r--; } return res;}int ans;void solve(int x){ ans+=work(x,0); vis[x]=1; for(int i=head[x];i!=-1;i=e[i].nxt){ int v=e[i].v; if(!vis[v]){ ans-=work(v,e[i].w); rt=0; getroot(v,rt,size[v]); solve(rt); } }}int main(){ while(~scanf("%d%d",&n,&k)){ if(n==0 && k==0)break; ans=0,rt=0; memset(head,-1,sizeof head);memset(vis,0,sizeof vis); cnt=0; memset(size,0,sizeof size); for(int i=1;i<n;i++){ int u,v,w;scanf("%d%d%d",&u,&v,&w); add(u,v,w);add(v,u,w); } f[0]=inf; getroot(1,0,n); solve(rt); printf("%d/n",ans); } return 0;}
新聞熱點
疑難解答