青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Tim's Programming Space  
Tim's Programming Space
日歷
<2010年1月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
31123456
統計
  • 隨筆 - 20
  • 文章 - 1
  • 評論 - 40
  • 引用 - 0

導航

常用鏈接

留言簿(3)

隨筆檔案

文章檔案

搜索

  •  

最新評論

閱讀排行榜

評論排行榜

 


題目敘述:
    給出一個有n個節點的樹, 一個整數k. 定義dist(u, v)為節點u, v間的距離. 求這棵樹中有多少節點對(u, v)滿足dist(u, v)<=k. (n<=10000)

-------------------------------------------

對于這樣一個數據范圍,顯然O(n^2)的直接算是會超時的。

大體的思路是:
    1.一個樹中的路徑可以分為兩種:一種是過根的,一種是不過根的--那一定是過子樹的根。所以可以對于每一棵樹都統計過根的路徑中長度小于等于K的有多少,然后加起來就是答案。
    2.對于每一棵子樹,找出子樹中所有點到根的距離,排序并統計路徑長度小于等于K的條數。對于一個有序的序列a,如果有i<j且a[i]+a[j]<=K,那么a[i] + a[i+1~j]<=K,所以可以找出對于一個i滿足條件最大的j或對于一個j滿足條件的最小的i,進行統計。
    3.這樣統計出來的路徑有些是從某個子樹到根后,又返回原來的子樹,顯然這樣的路徑是不滿足條件的。而這些路徑一定經過當前根的兒子,所以為了排除這些多余的路徑,只需要減去所有的在兒子的子樹中過兒子的路徑條數,當然,這些路徑長度并不是小于等于K了,而是小于等于K-2*根到兒子的邊的長度。
    4.這樣雖然能夠得到解,但是時間復雜度在一條鏈的情況下最壞為O(n^2logn)(n個點,每個點快排)。對于一個無根樹的統計,我們發現根的選擇是無關結果的。所以每次對于一棵子樹我們處理的時候,我們選擇的根不一定剛好就是上一個根的兒子,而可以是當前子樹當中的任意一個點,即每次把子樹看做一個無根圖來處理。而對于一個大小為n的無根樹,一定存在至少一個點是的以這個點作為根的樹的每個兒子的大小都不超過n/2。所以我們每次處理的時候就在當前的無根樹找到一個這樣的點,把它作為當前無根樹的根。這個點叫做樹的重心。這樣的話每次處理節點的數目至少會減少一半,所以處理的深度不會超過logn。這樣就把總的時間復雜度降到了O(nlognlogn)。

  1#include <iostream>
  2#include <cstdio>
  3#include <cstdlib>
  4#include <cstring>
  5#include <algorithm>
  6
  7#define MAXN 10000
  8#define MAXM MAXN*2
  9
 10using namespace std;
 11
 12int n,K;
 13int Count = 0;
 14int begin[MAXN+1],end[MAXM+1],next[MAXM+1],cost[MAXM+1];
 15void AddEdge(int a,int b,int c){
 16    Count++;
 17    next[Count] = begin[a];
 18    begin[a] = Count;
 19    end[Count] = b;
 20    cost[Count] = c;
 21}

 22void Solve();
 23void Init(){
 24    while (true){
 25        scanf("%d%d",&n,&K);
 26        if (n == 0 && K == 0)
 27            break;
 28        else
 29            Solve();
 30    }

 31}

 32
 33
 34bool hash[MAXN+1];
 35int size[MAXN+1];
 36int GetSize(int x,int fa){
 37    size[x] = 1;
 38    for (int now = begin[x]; now; now = next[now])
 39        if (!hash[end[now]] && end[now]!=fa)
 40            size[x] += GetSize(end[now],x);
 41    return size[x];
 42}

 43
 44int GetBestRoot(int x){
 45    GetSize(x,0);
 46    while (true){
 47        int MaxSize = 0,id = 0;
 48        for (int now = begin[x]; now; now = next[now])
 49            if (!hash[end[now]] && MaxSize < size[end[now]])
 50                MaxSize = size[id = end[now]];
 51        if (MaxSize <= (size[x] >> 1))
 52            break;
 53        size[x] -= size[id], size[id] += size[x], x = id;
 54    }

 55    return x;
 56}

 57int dist[MAXN+1];
 58int cnt;
 59void GetDist(int x,int fa,int d){
 60    if (d>K) return;
 61    dist[++cnt] = d;
 62    for (int now = begin[x]; now; now = next[now])
 63        if (!hash[end[now]] && end[now] != fa)
 64            GetDist(end[now],x,d + cost[now]);
 65}

 66int cmp(const void *a,const void *b){
 67    return (*(int *)a) - (*(int *)b);
 68}

 69int dfs(int x){
 70    x = GetBestRoot(x);
 71    hash[x] = true;
 72    int ret = 0;
 73    for (int now = begin[x]; now; now = next[now])
 74        if (!hash[end[now]])
 75            ret += dfs(end[now]);
 76    cnt = 0;
 77    GetDist(x,0,0);
 78    qsort(dist+1,cnt,sizeof(dist[0]),cmp);
 79    
 80    
 81    int l = 1, r = cnt;
 82    while (l<r){
 83        if (dist[l] + dist[r]<=K) ret += r-l, l++;
 84        else r--;
 85    }

 86    for (int now = begin[x]; now; now = next[now])
 87        if (!hash[end[now]]){
 88            int limit = K - cost[now] * 2;
 89            cnt = 0;
 90            GetDist(end[now],00);
 91            qsort(dist+1,cnt,sizeof(dist[0]),cmp);
 92            int l = 1, r = cnt;
 93            while (l<r){
 94                if (dist[l] + dist[r]<=limit) ret -= r-l, l++;
 95                else r--;
 96            }

 97        }

 98    hash[x] = false;
 99    return ret;
100}

101
102void Solve(){
103    Count = 0;
104    memset(begin,0,sizeof(begin));
105    int t1,t2,t3;
106    for (int i = 1; i<n; i++){
107        scanf("%d%d%d",&t1,&t2,&t3);
108        AddEdge(t1,t2,t3);
109        AddEdge(t2,t1,t3);
110    }

111    printf("%d\n",dfs(1));
112}

113
114int main(){
115    Init();
116    return 0;
117}

118
posted on 2010-01-05 16:23 TimTopCoder 閱讀(2315) 評論(5)  編輯 收藏 引用
評論:
  • # re: 男人8題之 Tree (pku 1741)[未登錄]  forestkeeper Posted @ 2010-01-05 21:38
    樹形dp+歸并排序的方法,lz的代碼如果用vector能更簡潔

    dp[i][j]表示以i為根的子樹長度為j的點對數  回復  更多評論   

  • # re: 男人8題之 Tree (pku 1741)  TimTopCoder Posted @ 2010-01-07 10:47
    @forestkeeper
    可能子樹的長度很長,你的那種方法空間和時間都無法承受啊!  回復  更多評論   

  • # re: 男人8題之 Tree (pku 1741)  forestkeeper Posted @ 2010-01-09 11:11
    @TimTopCoder
    恩,沒A過那題,去A下。。。  回復  更多評論   

  • # re: 男人8題之 Tree (pku 1741)  popzkk Posted @ 2010-03-15 15:26
    受益匪淺, 非常感謝!!!
      回復  更多評論   

 
Copyright © TimTopCoder Powered by: 博客園 模板提供:滬江博客
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            久久香蕉国产线看观看av| 亚洲第一区色| 国产日韩亚洲| 亚洲视频网站在线观看| 老鸭窝91久久精品色噜噜导演| 亚洲国产小视频| 亚洲在线视频免费观看| 欧美日韩国产小视频在线观看| 亚洲国产视频一区二区| 免费h精品视频在线播放| 久久国产视频网站| 国产日韩欧美另类| 久久精品1区| 亚洲直播在线一区| 国产精品一区二区欧美| 欧美一区二区三区男人的天堂| 一区二区三区欧美视频| 欧美日韩在线观看视频| 亚洲一区二区欧美日韩| 亚洲天堂av在线免费观看| 欧美小视频在线观看| 午夜精品一区二区三区四区| 亚洲专区一区| 黑人巨大精品欧美黑白配亚洲| 久久精品国产精品亚洲精品| 欧美在线视频一区二区| 亚洲第一在线视频| 亚洲国产日韩一区| 欧美午夜久久久| 久久se精品一区精品二区| 久久精品视频在线看| 在线观看欧美激情| 亚洲激情二区| 国产精品毛片a∨一区二区三区|国 | 男人插女人欧美| 亚洲精品欧美极品| 在线中文字幕一区| 国产深夜精品福利| 欧美成人免费在线视频| 国产精品99免费看 | 亚洲精品欧美在线| 欧美午夜免费影院| 久久激情五月婷婷| 蜜臀久久99精品久久久久久9| 亚洲伦理中文字幕| 亚洲欧美另类在线| 亚洲人成人一区二区三区| 一区二区日韩伦理片| 在线播放国产一区中文字幕剧情欧美| 亚洲激情图片小说视频| 国产伦精品免费视频| 亚洲人午夜精品免费| 国产亚洲精品资源在线26u| 欧美成人一区二区三区| 亚洲美女免费视频| 国产亚洲精品久| 亚洲国产精品综合| 国产日韩欧美综合在线| 亚洲精选一区二区| 在线观看一区| 亚洲一区二区三区色| 亚洲国产精品久久精品怡红院 | 国产精品亚洲综合一区在线观看| 欧美大香线蕉线伊人久久国产精品| 欧美午夜宅男影院在线观看| 欧美高清一区二区| 国产欧美日韩另类一区 | 欧美精品亚洲二区| 另类欧美日韩国产在线| 国产精品人成在线观看免费| 亚洲第一久久影院| 国产一区二区三区在线观看免费| 一本色道久久加勒比88综合| 在线色欧美三级视频| 欧美一区二区日韩一区二区| 亚洲图片在区色| 欧美国产日韩一区二区| 美女主播一区| 国产在线播放一区二区三区| 亚洲一区二区在线看| 在线亚洲一区二区| 欧美人成免费网站| 亚洲欧洲另类| 亚洲精品欧美| 欧美国产免费| 亚洲国产第一| 亚洲国产精品成人va在线观看| 欧美一区二区视频网站| 久久精品国产亚洲一区二区| 国产日韩精品在线| 欧美一区二区三区精品电影| 午夜日韩在线| 国产精品婷婷| 亚洲欧美日韩在线一区| 性欧美1819sex性高清| 国产精品久久久久久久久婷婷| 亚洲视频精品在线| 欧美精品在线观看播放| 欧美一区二区视频97| 亚洲尤物精选| 亚洲综合视频网| 亚洲伊人伊色伊影伊综合网| 国产主播一区二区| 国产午夜精品美女视频明星a级| 欧美系列精品| 国产一区二区黄色| 在线观看国产精品淫| 精品二区视频| 99亚洲视频| 香蕉尹人综合在线观看| 欧美在线播放一区| 狼人社综合社区| 欧美金8天国| 欧美人与禽性xxxxx杂性| 欧美一级欧美一级在线播放| 欧美顶级大胆免费视频| 亚洲午夜91| 亚洲美女一区| 亚洲免费观看在线观看| 亚洲特级片在线| 国产精品卡一卡二卡三| 免费成人高清| 韩国v欧美v日本v亚洲v| 国产精品一区二区黑丝| 亚洲免费在线观看| 欧美一区二区视频97| 激情文学综合丁香| 欧美日韩激情小视频| 午夜国产精品视频| 亚洲第一视频| 午夜在线播放视频欧美| 狠狠色狠狠色综合系列| 欧美精品亚洲精品| 欧美一区二区女人| 亚洲日本黄色| 久久精品一级爱片| 伊人久久噜噜噜躁狠狠躁| 久久国产黑丝| 一区二区三区日韩精品视频| 免费一级欧美片在线观看| 国产精品久久久99| 亚洲一区三区电影在线观看| 亚洲激情亚洲| 国产精品99一区| 性久久久久久| 欧美综合二区| 亚洲国产国产亚洲一二三| 久久在线91| 午夜精品久久久99热福利| 久久亚洲二区| 久久国产天堂福利天堂| 国产一区二区三区在线观看网站 | 欧美久久视频| 99re热这里只有精品视频| 久久精品欧美日韩| 欧美激情国产日韩精品一区18| 欧美极品在线播放| 亚洲黄色免费电影| 午夜一级在线看亚洲| 久色成人在线| 亚洲欧美制服中文字幕| 99国产成+人+综合+亚洲欧美| 香蕉免费一区二区三区在线观看| 欧美日韩另类视频| 久久综合亚洲社区| 欧美一区二区三区的| 亚洲午夜伦理| 亚洲精品久久久久久久久| 麻豆国产精品777777在线| 欧美伊人久久大香线蕉综合69| 日韩午夜av| 亚洲免费观看| 亚洲精品乱码久久久久久日本蜜臀| 国内偷自视频区视频综合| 国产日韩综合| 国产区在线观看成人精品| 国产毛片精品视频| 国产欧美日韩精品a在线观看| 国产精品久久久久一区二区| 欧美在线黄色| 欧美成人免费大片| 久久久久久久激情视频| 欧美激情aaaa| 欧美激情aⅴ一区二区三区| 国模私拍视频一区| 亚洲一区二区久久| 亚洲尤物在线| 国产欧美亚洲精品| 亚洲欧美久久久久一区二区三区| 亚洲午夜精品福利| 国产精品国产三级国产专播品爱网 | 久久久久免费视频| 国产精品二区二区三区| 欧美制服丝袜| 老司机精品久久| 一区二区三区四区五区精品| 亚洲免费在线播放| 久久亚洲综合| 另类国产ts人妖高潮视频| 欧美mv日韩mv亚洲|