题目链接：传送门

Description

有n个城市，有些城市被设定成集市 ，每个城市只能到离他最近的并且编号最小的集市，现在如果再建一个集市，那么最多有多少个城市可以到这个集市

Solution

先跑一遍SPFA最短路，求出每个城市到最近的集市的距离和编号，然后点分治。对于树上的节点u，v，如果 dis[u] + dis[v] < near[v]（dis表示节点到根的距离，near表示接地离最近集市的距离），那么如果在节点u建立集市，那么节点v肯定会到u，把式子变形，得到dis[u] < near[v] - dis[v];那么只需要二分就可以求出有多少个节点到达u

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1e5 + 100, inf = INT_MAX;

int N, M, K;
int Begin[Maxn], To[Maxn * 2], Next[Maxn * 2], W[Maxn * 2], e;
int Ans[Maxn], Vis[Maxn];
int type[Maxn];

struct node
{
    int x, y;
    bool operator < (const node &a) const
    {
        if (x == a.x) return y < a.y;
        return x < a.x;
    }
}near[Maxn], q[Maxn];

inline void Init()
{
    e = 0;
    memset(Begin, 0, sizeof Begin);
    memset(Ans, 0, sizeof Ans);
    memset(Vis, 0, sizeof Vis);
}

inline void add_edge (int x, int y, int z)
{
    To[++e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
    W[e] = z;
}

inline void SPFA ()
{
    queue <int> Q;
    memset(Vis, 0, sizeof Vis);
    for (int i = 1; i <= N; ++i)
        if (type[i])
            Q.push(i), Vis[i] = 1, near[i] = {0, i};
        else near[i] = {inf, 0};
    while (!Q.empty())
    {
        int x = Q.front();
        //cout<<x<<endl;
        Q.pop();
        Vis[x] = 0;
        for (int i = Begin[x]; i; i = Next[i])
        {
            int y = To[i];
            //cout<<y<<" ";
            if (near[y].x > near[x].x + W[i])
            {
                near[y].x = near[x].x + W[i];
                near[y].y = near[x].y;
                if (!Vis[y])
                {
                    Vis[y] = 1;
                    Q.push(y);
                }
            }
        }
        //cout<<endl;
    }
}

int pos, Min;
int size[Maxn];

inline void dfs1 (int x, int fa)
{
    size[x] = 1;
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (Vis[y] || y == fa) continue;
        dfs1 (y, x);
        size[x] += size[y];
    }
}

inline void dfs2 (int x, int fa, int Size)
{
    int tmp = Size - size[x];
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (y == fa || Vis[y]) continue;
        dfs2 (y, x, Size);
        tmp = max(tmp, size[y]);
    }
    if (tmp < Min)
    {
        Min = tmp;
        pos = x;
    }
}

int cnt;
int rec[Maxn], Dis[Maxn];

inline void dfs (int x, int fa, int dis)
{
    Dis[x] = dis;
    rec[++cnt] = x;
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (y == fa || Vis[y]) continue;
        dfs (y, x, dis + W[i]);
    }
}

inline void Calc (int x, int d, int f)
{
    //cout<<x<<" "<<d<<endl;
    cnt = 0;
    dfs(x, 0, d);

    for (int i = 1; i <= cnt; ++i)
        q[i].x = near[rec[i]].x - Dis[rec[i]], q[i].y = near[rec[i]].y;

    sort(q + 1, q + cnt + 1);
//  for (int i = 1; i <= cnt; ++i)
//      cout<<q[i].x<<" "<<q[i].y<<endl;
//  cout<<endl;

    for (int i = 1; i <= cnt; ++i)
    {
        int x = rec[i];
        if (!type[x])
        {
            node tmp = {Dis[x], x};
            int p = lower_bound(q + 1, q + cnt + 1, tmp) - q;
    //      cout<<"*"<<p<<endl;
            Ans[x] += f * (cnt - p + 1);
        }
    }
}

inline void Devide (int x)
{
    Min = inf;
    dfs1(x, 0);
    dfs2(x, 0, size[x]);

    x = pos;
    Calc(x, 0, 1);
    Vis[x] = 1;

    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (Vis[y]) continue;
        Calc(y, W[i], -1);
        Devide(y);
    }
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    while (~scanf("%d", &N))
    {
        Init();
        for (int i = 1; i < N; ++i)
        {
            int x, y, z ;
            scanf("%d%d%d", &x, &y, &z);
            add_edge(x, y, z);
            add_edge(y, x, z);
        }
        for (int i = 1; i <= N; ++i) scanf("%d", &type[i]);

        SPFA();
        //for (int i = 1; i <= N; ++i)
        //  printf("%d %d\n", near[i].x, near[i].y), fflush(stdout);
        Devide(1);

        int ans = 0;
        for (int i = 1; i <= N; ++i) ans = max(ans, Ans[i]);
        cout<<ans<<endl;
    }
    return 0;
}
//注意i和rec[i]不要搞混