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
| namespace NodeDAC{
int rt=0,judge[MAXK],all[MAXK],dp[MAXN],son[MAXN],sz[MAXN],cnt,Ans[MAXN],sum,Q[MAXN],dis[MAXN];
bool vis[MAXN];
inline void getroot(int u, int fa=-1){
dp[u] = 0, sz[u] = 1;
trav(i,u){
int v = edge[i].v;
if (vis[v] || v==fa) continue;
getroot(v,u);
sz[u]+=sz[v];
dp[u] = chkmax(dp[u],sz[v]);
}
dp[u] = chkmax(dp[u],sum-sz[u]);
if (dp[u]<dp[rt]) rt = u;
}
inline void getdis(int u, int fa){
if (dis[u]<=(int)1e7)judge[++cnt] = dis[u];
trav(i,u){
int v = edge[i].v,d = edge[i].d;
if (vis[v] || v==fa) continue;
dis[v] = dis[u]+d;
getdis(v,u);
}
}
int q[MAXK];
inline void calc(int u){
int ptr = 0;
trav(i,u){
int v = edge[i].v, d = edge[i].d;
if (vis[v]) continue;
cnt = 0;
dis[v] = d;
getdis(v,u);
FOR(j,cnt,1) For(l,1,m) if (Q[l]>=judge[j]) Ans[l]|=all[Q[l]-judge[j]];
FOR(j,cnt,1) q[++ptr] = judge[j],all[judge[j]] = true;
}
For(i,1,ptr) all[q[i]] = 0;
}
inline void divide(int u=rt){
vis[u] = all[0] = true;
calc(u);
trav(i,u){
int v = edge[i].v;
if (vis[v]) continue;
sum = sz[v]; dp[rt=0] = n;
getroot(v,u);
divide(rt);
}
}
}
|
