原題地址：http://poj.org/problem?id=2114

題目大意：

給定一棵點數為\(n~(n \le 10000)\)的無根樹，路徑上有權值，給出m組詢問（$m \le 100$），每組詢問給出一個k，問樹中是否存在長度為k的鏈。題目是多case

題目分析：

這是第二次寫樹分治，細節想清楚真的很重要啊。。。寫了兩天才寫過，接下來說一說算法流程和需要注意的細節吧

首先讀入、建圖等等等等。。

然后是分治過程：

0.如果當前處理的這棵樹的size很小了，調用暴力解決，否則繼續執行（這相當于邊界處理）

1.找出當前要處理的樹的重心作為分治點

2.算出重心到這棵樹中每個點的距離，掃出來是否有兩個點的距離和等于要詢問的值，有則加上對數

3.將重心發出的所有邊斷開，計算每棵子樹中到重心距離和為k的點對，在答案中減去

4.遞歸處理所有子樹，根據最終得到的個數判斷是否存在

分治過程看起來很簡單，但是有幾個細節需要注意：斷邊的時候斷開鄰接表需要小心。每一次遞歸我們都需要初始化一些變量，但是每次全部初始化的代價過于高昂，而且會影響到當前樹中沒有的節點，每次初始化都BFS一遍過于麻煩，所有可以開若干個vector表示當前遞歸處理的子樹中的點，然后就可以減少復雜度。計算距離之后需要排序去重以便高效地計算出要求的值。

（準備省選過于忙碌了一直沒來得及寫什么總結……學了不少新知識回頭都得抓緊總結了）

1 //date 20140417 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 7 const int maxn = 10500; 8 const int INF = 0x7FFFFFFF; 9 const int r1 = 2; 10 11 using namespace std; 12 typedef vector<int> array; 13 typedef array::iterator iter; 14 typedef vector<array>::iterator viter; 15 16 inline int getint() 17 { 18 int ans(0); char w = getchar(); 19 while(w < '0' || '9' < w)w = getchar(); 20 while('0' <= w && w <= '9') 21 { 22 ans = ans * 10 + w - '0'; 23 w = getchar(); 24 } 25 return ans; 26 } 27 28 inline int innew(int &a, int b){if(a < b){a = b; return 1;}return 0;} 29 inline int denew(int &a, int b){if(a > b){a = b; return 1;}return 0;} 30 31 struct edge 32 { 33 int v, w, next; 34 }E[maxn << 1]; 35 int a[maxn], nedge; 36 int n; 37 int ask[maxn], ans[maxn], nsk; 38 39 vector<array> P; 40 array tmp; 41 42 inline void add(int u, int v, int w) 43 { 44 E[++nedge].v = v; 45 E[nedge].w = w; 46 E[nedge].next = a[u]; 47 a[u] = nedge; 48 } 49 50 namespace d_c 51 { 52 int yff, dis[maxn], list[maxn], size[maxn], p[maxn]; 53 int q[maxn], st, ed; 54 int d[maxn], last, now[maxn], had[maxn]; 55 int tlist[maxn], ttot, plist[maxn]; 56 57 inline int getcend(int k, int yff) 58 { 59 for(iter i = P[k].begin(); i != P[k].end(); ++i) 60 { 61 size[*i] = p[*i] = 0; now[*i] = a[*i]; 62 } 63 size[d[last = 1] = P[k][0]] = 1; 64 while(last) 65 { 66 int i = d[last], j = now[i]; 67 if(!j) 68 { 69 if(--last) size[d[last]] += size[i]; 70 continue; 71 } 72 if(!size[E[j].v]) 73 { 74 size[d[++last] = E[j].v] = 1; 75 p[E[j].v] = i; 76 } 77 now[i] = E[j].next; 78 } 79 int Max, ans, Min = INF; 80 for(iter i = P[k].begin(); i != P[k].end(); ++i) 81 { 82 Max = yff - size[*i]; 83 for(int j = a[*i]; j; j = E[j].next)if(p[*i] != E[j].v) 84 innew(Max, size[E[j].v]); 85 if(denew(Min, Max))ans = *i; 86 } 87 if(p[ans])size[p[ans]] = yff - size[ans]; 88 return ans; 89 } 90 91 inline void brutf(int k, int yff) 92 { 93 for(iter i = P[k].begin(); i != P[k].end(); ++i) 94 { 95 for(iter j = P[k].begin(); j != P[k].end(); ++j)dis[*j] = list[*j] = 0; 96 int st = 0, ed = 1, tot; 97 q[dis[*i] = 1] = *i; 98 while(st < ed) 99 { 100 int x = q[++st]; 101 for(int i = a[x]; i; i = E[i].next)if(!dis[E[i].v]) 102 dis[q[++ed] = E[i].v] = dis[x] + E[i].w; 103 } 104 for(iter j = P[k].begin(); j != P[k].end(); ++j) 105 for(int need = 1; need <= nsk; ++need) 106 ans[need] += (dis[*j] == ask[need] + 1) << 1; 107 } 108 } 109 110 inline void main(int k) 111 { 112 yff = P[k].size(); 113 if(yff <= r1){brutf(k, yff); return;} 114 int cend = getcend(k, yff); 115 for(iter i = P[k].begin(); i != P[k].end(); ++i) dis[*i] = had[*i] = 0; 116 st = 0; ed = 1; int tot; 117 list[dis[q[1] = cend] = tot = 1] = 1; 118 while(st < ed) 119 { 120 int x = q[++st]; 121 for(int i = a[x]; i; i = E[i].next)if(!dis[E[i].v]) 122 { 123 list[++tot] = dis[q[++ed] = E[i].v] = dis[x] + E[i].w; 124 } 125 } 126 127 sort(list + 1, list + tot + 1); 128 tlist[plist[1] = ttot = 1] = list[1]; 129 for(int i = 2; i <= tot; ++i) 130 { 131 if(list[i] == list[i - 1])++plist[ttot]; 132 else {tlist[++ttot] = list[i]; plist[ttot] = 1;} 133 } 134 135 for(int need = 1; need <= nsk; ++need) 136 { 137 int j = ttot; 138 for(int i = 1; i <= ttot; ++i) 139 { 140 while(j && (tlist[j] + tlist[i] > ask[need] + 2))--j; 141 if(!j)break; 142 if(tlist[j] + tlist[i] == ask[need] + 2) 143 { 144 if(j != i)ans[need] += plist[i] * plist[j]; 145 else ans[need] += plist[i] * (plist[i] - 1); 146 } 147 } 148 } 149 150 for(int i = a[cend]; i; i = E[i].next) 151 { 152 int sign = 0; 153 if(a[E[i].v] == (i ^ 1)){a[E[i].v] = E[i ^ 1].next;} 154 else 155 { 156 int last; 157 for(int j = a[E[i].v]; j != (i ^ 1); j = E[j].next) last = j; 158 E[last].next = E[i ^ 1].next; 159 } 160 tmp.clear(); 161 st = 0; ed = 1; q[had[E[i].v] = 1] = E[i].v; 162 tmp.push_back(E[i].v); 163 list[tot = 1] = dis[E[i].v]; 164 while(st < ed) 165 { 166 int x = q[++st]; 167 for(int j = a[x]; j; j = E[j].next) 168 if(!had[E[j].v]){tmp.push_back(E[j].v); had[E[j].v] = 1; q[++ed] = E[j].v; list[++tot] = dis[E[j].v];} 169 } 170 sort(list + 1, list + tot + 1); 171 tlist[plist[1] = ttot = 1] = list[1]; 172 for(int w = 2; w <= tot; ++w) 173 { 174 if(list[w] == list[w - 1])++plist[ttot]; 175 else {tlist[++ttot] = list[w]; plist[ttot] = 1;} 176 } 177 178 for(int need = 1; need <= nsk; ++need) 179 { 180 int j = ttot; 181 for(int w = 1; w <= ttot; ++w) 182 { 183 while(j && (tlist[j] + tlist[w] > ask[need] + 2))--j; 184 if(!j)break; 185 if(tlist[w] + tlist[j] == ask[need] + 2) 186 { 187 if(j != w)ans[need] -= plist[w] * plist[j]; 188 else ans[need] -= plist[w] * (plist[w] - 1); 189 } 190 } 191 } 192 193 P.push_back(tmp); 194 main(P.size() - 1); 195 } 196 197 } 198 } 199 200 int main() 201 { 202 while(true) 203 { 204 n = getint(); 205 if(!n)break; 206 P.clear(); tmp.clear(); 207 memset(a, 0, sizeof a); 208 memset(ans, 0, sizeof ans); 209 nedge = 1; 210 211 for(int i = 1; i <= n; ++i)tmp.push_back(i); 212 P.push_back(tmp); 213 214 for(int i = 1; i <= n; ++i) 215 { 216 int x, w; 217 while(true) 218 { 219 x = getint(); 220 if(!x)break; 221 w = getint(); 222 add(i, x, w); add(x, i, w); 223 } 224 } 225 nsk = 0; 226 while(true) 227 { 228 ask[++nsk] = getint(); 229 if(!ask[nsk]){--nsk; break;} 230 } 231 d_c::main(0); 232 for(int i = 1; i <= nsk; ++i)printf("%s\n", ans[i] > 0 ? "AYE" : "NAY"); 233 printf(".\n"); 234 } 235 236 return 0; 237 }

?

轉載于:https://www.cnblogs.com/w007878/p/3672063.html

總結

以上是生活随笔為你收集整理的POJ 2114 - Boatherds的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。