题意：给定一个n个点的图，这个图是一棵树，然后有些点建立了集市。并且没有集市的地方去集市一定是去最近的，如果距离相同，那么则去标号最小的。。现在你还能在建一个集市，问建完这个集市最多有多少个点来这里。。
思路：
现对于每个点求该点到有标记点最近的距离，记录距离及其最近标号，可以用树形dp或者spfa搞。。
然后我们任意选定一个点建树，建完后进行点分治。。
对于当前分治快的跟rt，求rt到每个点的距离为dis，near为到标记点最近的距离
那么对于不同子树的点u,v,如果dis[u] + dis[v] < near[v]，那么如果u建立集市v肯定到u。。
那么我们把式子变形下，dis[u] < near[v] - dis[v],对于u直接二分查找统计即可。。
我们可以先不管哪棵子树先统计一边，然后再减去相同的即可，这样写起来方便点。。写起来还蛮像poj1741的。。
code：
1 /* 2 * Author: Yzcstc 3 * Created Time: 2014/10/2 17:37:34 4 * File Name: hdu5016.cpp 5 */ 6 #pragma comment(linker, "/STACK:102400000,102400000") 7 #include<cstdio> 8 #include<iostream> 9 #include<cstring> 10 #include<cstdlib> 11 #include<cmath> 12 #include<algorithm> 13 #include<string> 14 #include<map> 15 #include<set> 16 #include<vector> 17 #include<queue> 18 #include<stack> 19 #include<ctime> 20 #define repf(i, a, b) for (int i = (a); i <= (b); ++i) 21 #define repd(i, a, b) for (int i = (a); i >= (b); --i) 22 #define M0(x) memset(x, 0, sizeof(x)) 23 #define clr(x, y) memset(x, y, sizeof(x)) 24 #define N 120000 25 #define Inf 0x3fffffff 26 #define x first 27 #define y second 28 using namespace std; 29 typedef pair<int, int> pii; 30 struct edge{ 31 int v, w, next; 32 edge(){} 33 edge(int _v, int _w, int _next):v(_v), w(_w), next(_next){} 34 } e[N<<1]; 35 int last[N], n, len, have[N], ans[N]; 36 int inq[N]; 37 pii ner[N]; 38 39 void add(int u, int v, int w){ 40 e[len] = edge(v, w, last[u]), last[u] = len++; 41 } 42 43 void init(){ 44 clr(last, -1); 45 len = 0; 46 int u, v, w; 47 for (int i = 1; i < n; ++i){ 48 scanf("%d%d%d", &u, &v, &w); 49 add(u, v, w), add(v, u, w); 50 } 51 repf(i, 1, n) scanf("%d", &have[i]); 52 } 53 54 void gao(){ 55 repf(i, 0, n) ner[i].x = ner[i].y = Inf, inq[i] = 0; 56 queue<int> q; 57 repf(i, 1, n) if (have[i]){ 58 ner[i].x = 0, ner[i].y = i; 59 q.push(i), inq[i] = 1; 60 } 61 int u, v; 62 pii tmp; 63 while (!q.empty()){ 64 u = q.front(); 65 q.pop(), inq[u] = 0; 66 for (int p = last[u]; ~p; p = e[p].next){ 67 v = e[p].v; 68 tmp.x = ner[u].x + e[p].w, tmp.y = ner[u].y; 69 if (tmp < ner[v]){ 70 ner[v] = tmp; 71 if (!inq[v]) inq[v] = 1, q.push(v); 72 } 73 } 74 } 75 76 } 77 /*** 点分治-begin **/ 78 int vis[N], sz, msize[N], f[N], size[N], belong[N], ss, ff[N]; 79 int dis[N]; 80 pair<int, int> s[N], tp; 81 82 void dfs(int u, int fa){ //calculate the size 83 f[sz++] = u; 84 msize[u] = 0, size[u] = 1; 85 int v; 86 for (int p = last[u]; ~p; p = e[p].next){ 87 v = e[p].v; 88 if (v == fa || vis[v]) continue; 89 dfs(v, u); 90 size[u] += size[v]; 91 msize[u] = max(size[v], msize[u]); 92 } 93 } 94 95 void dfs(int u, int fa, int dist){ 96 dis[u] = dist, ff[ss++] = u; 97 int v; 98 for (int p = last[u]; ~p; p = e[p].next){ 99 v = e[p].v; 100 if (v == fa || vis[v]) continue; 101 dfs(v, u, dist + e[p].w); 102 } 103 } 104 105 void calculate(int u, int dist){ 106 ss = 0; 107 dfs(u, 0, dist); 108 for (int i = 0; i < ss; ++i) 109 s[i].x = ner[ff[i]].x - dis[ff[i]], s[i].y = ner[ff[i]].y; 110 sort(s, s+ss); 111 int t; 112 for (int i = 0; i < ss; ++i) if (!have[ff[i]]){ 113 tp.x = dis[ff[i]], tp.y = ff[i]; 114 t = lower_bound(s, s+ss, tp) - s; 115 ans[ff[i]] += (dist > 0) ? (t - ss) : (ss - t); 116 } 117 } 118 119 void dfs(int u){ 120 sz = 0; 121 dfs(u, 0); 122 int rt = 0, tmp, v; 123 for (int i = 0; i < sz; ++i){ 124 tmp = max(msize[f[i]], sz-1-size[f[i]]); 125 if (tmp <= (sz>>1)) { rt = f[i]; break; } 126 } 127 calculate(rt, 0); 128 vis[rt] = 1; 129 for (int p = last[rt]; ~p; p = e[p].next){ 130 v = e[p].v; 131 if (vis[v]) continue; 132 calculate(v, e[p].w); 133 dfs(v); 134 } 135 } 136 /**** 点分治-end***/ 137 138 void solve(){ 139 gao(); 140 M0(vis); 141 M0(ans); 142 dfs(1); 143 int mx = 0; 144 for (int i = 1; i <= n; ++i) 145 mx = max(ans[i], mx); 146 printf("%d ", mx); 147 } 148 149 int main(){ 150 // freopen("a.in", "r", stdin); 151 // freopen("a.out", "w", stdout); 152 while (scanf("%d", &n) != EOF){ 153 init(); 154 solve(); 155 } 156 return 0; 157 }