# Nemlit 的博客

By a konjac

### 题解 P3233 【[HNOI2014]世界树】

posted on 2019-09-30 22:40:28 | under 题解 |

## 献上十分丑陋的代码：

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define drep(i, s, t) for(re int i = t; i >= s; -- i)
#define Next(i, u) for(re int i = head[u]; i; i = e[i].next)
#define _ 300005
int n, m, Q, top[_], Top, st[_], son[_], size[_], dep[_], dfn[_], tot, cnt, head[_];
int id[_], ans[_], f[25][_], dis[_], vis[_], Size[_];
struct node {int a, id;}q[_];
struct edge {int v, next, w;}e[_ << 1];
il bool cmp(node a, node b) {return dfn[a.a] < dfn[b.a];}
il bool cmp1(node a, node b) {return a.id < b.id;}
il void add(int u, int v, int w) {
}
il void dfs1(int u, int fr) {
f[0][u] = fr, dep[u] = dep[fr] + 1, size[u] = 1, dfn[u] = ++ tot;
Next(i, u) if(e[i].v != fr) dfs1(e[i].v, u), size[u] += size[e[i].v];
}
il int LCA(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
drep(i, 0, 20) if(dep[a] - (1 << i) >= dep[b]) a = f[i][a];
drep(i, 0, 20) if(f[i][a] != f[i][b]) a = f[i][a], b = f[i][b];
return (a == b) ? a : f[0][a];
}
il int Dis(int a, int b) {return dep[a] + dep[b] - dep[LCA(a, b)] * 2;}
il void insert(int x) {
if(Top == 1 && x != 1) return (void)(st[++ Top] = x);
int lca = LCA(st[Top], x);  if(lca == x) return;
while(Top > 1 && dep[st[Top - 1]] > dep[lca])
add(st[Top - 1], st[Top], Dis(st[Top - 1], st[Top])), -- Top;
if(dep[st[Top]] > dep[lca]) add(st[Top], lca, Dis(st[Top], lca)), -- Top;
if(dep[st[Top]] < dep[lca]) st[++ Top] = lca;
st[++ Top] = x;
}
il void dfs_mem(int u, int fr) {
Next(i, u) if(e[i].v != fr) dfs_mem(e[i].v, u);
head[u] = vis[u] = id[u] = dis[u] = Size[u] = ans[u] = 0;
}
il int get_fa(int u, int dis) {
int now = 0;
drep(i, 0, 20) if(now + (1 << i) <= dis) now += (1 << i), u = f[i][u];
return u;
}
il void dfs_get(int u, int fr) {
if(vis[u]) dis[u] = 0, id[u] = u, Size[u] = size[u];
else dis[u] = 123456789, Size[u] = size[u];
Next(i, u) {
int v = e[i].v, w = e[i].w;  if(v == fr) continue;
dfs_get(v, u), w += dis[v];
if(dis[u] > w || (dis[u] == w && id[u] > id[v])) dis[u] = w, id[u] = id[v];
}
}
il void dfs1_get(int u, int fr) {
Next(i, u) {
int v = e[i].v, w = dis[u] + e[i].w;  if(v == fr) continue;
if(w < dis[v] || (w == dis[v] && id[v] > id[u])) dis[v] = w, id[v] = id[u];
dfs1_get(v, u);
if(id[u] == id[v]) Size[u] -= size[v];
else {
int x = get_fa(v, (dis[v] + dis[u] + e[i].w + (id[u] > id[v]) - 1) / 2 - dis[v]);//Attention: (dep[x] - dep[y])即e[i].w的意义是经过的边的数量！我就是因为这里调了**的
Size[v] += size[x] - size[v], Size[u] -= size[x];
}
ans[id[v]] += Size[v];
}
if(u == 1) ans[id[1]] += Size[1];
}
int main() {
}