## 【Codeforces 757F】Team Rocket Rises Again

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;
const int M = 600000+9;
const LL INF = 1e9 * 1e9;

LL dis[N];
int n,m,s,E,vout,fa[N][20],done[N],in[N];
priority_queue<pair<LL,int> > que;
vector<int> anc[N],son[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v, int c = 0) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;
}

inline void Dijkstra() {
memset(dis,60,sizeof(dis));
dis[s] = 0; que.push(make_pair(0, s));

while (!que.empty()) {
int w = que.top().second; que.pop();
if (!done[w]) done[w] = 1;
else continue;
if (dis[to[i]] > dis[w] + cost[i]) {
dis[to[i]] = dis[w] + cost[i];
que.push(make_pair(-dis[to[i]], to[i]));
}
}
}
}

inline int LCA(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i=19;~i;i--) if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
if (u == v) return u;
for (int i=19;~i;i--) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
return fa[u][0];
}

void solve(int w) {
done[w] = 1;
int f = anc[w][0];
for (int i=1;i<(int)anc[w].size();i++)
f = LCA(f, anc[w][i]);
fa[w][0] = f; dep[w] = dep[f] + 1;
for (int i=1;i<20;i++)
fa[w][i] = fa[fa[w][i-1]][i-1];
for (int i=son[w].size()-1,t;~i;i--) {
t = son[w][i];
if (--in[t] == 0 && !done[t]) {
solve(t);
}
}
}

int DFS(int w, int f) {
int sz = 1;
if (to[i] != f) {
sz += DFS(to[i], w);
}
}
if (w != s) vout = max(vout, sz);
return sz;
}

int main() {
for (int i=1,u,v;i<=m;i++) {
}
Dijkstra();
for (int w=1;w<=n;w++) {
if (dis[w] > INF) continue;
if (dis[to[i]] == dis[w] + cost[i]) {
anc[to[i]].push_back(w);
son[w].push_back(to[i]);
in[to[i]] += (w != s);
}
}
}
memset(done,0,sizeof(done));
done[s] = 1; E = 0;
for (int i=0;i<20;i++) fa[s][i] = s;
for (int i=1;i<=n;i++) {
if (!in[i] && !done[i] && dis[i] < INF) {
solve(i);
}
}
DFS(s, s);
printf("%d\n",vout);
return 0;
}


## 【BZOJ 2851】极限满月

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;
const int M = N*200;

int que[N],fa[N][18],dep[N],num_cnt;
vector<int> G[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void Add_Edge(int u, int v) {
static int T = 0; in[v]++;
}

inline bool cmp(const int &a, const int &b) {
return in[a] < in[b];
}

inline int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i=17;~i;i--) {
if (dep[fa[x][i]] >= dep[y]) {
x = fa[x][i];
}
}
if (x == y) return y;
for (int i=17;~i;i--) {
if (fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}

inline void solve(int w) {
dep[w] = dep[fa[w][0]] + 1;
if (w) G[fa[w][0]].push_back(w);
for (int i=1;i<=17;i++) {
fa[w][i] = fa[fa[w][i-1]][i-1];
}

if (!~fa[to[i]][0]) {
fa[to[i]][0] = w;
} else {
fa[to[i]][0] = lca(fa[to[i]][0], w);
}

if (!--in[to[i]]) solve(to[i]);
}
}

void DFS(int w) {
in[w] = ++num_cnt;
for (int i=G[w].size()-1;~i;i--) {
DFS(G[w][i]);
}
out[w] = num_cnt;
}

int main(){
memset(fa,-1,sizeof(fa));
for (int i=1;i<=n;i++) {
}
if (!in[i]) {
}
}

fa[0][0] = 0;
solve(0);
DFS(0);

for (int k=1,len,vout=0;k<=m;k++,vout=0) {
for (int j=1;j<=len;j++) {
}

sort(que+1,que+1+len,cmp);
for (int i=1,pre=0;i<=len;i++) {
vout += dep[que[i]];
vout -= dep[lca(pre,que[i])];
pre = que[i];
}

printf("%d\n",vout);
}
return 0;
}


—– UPD 2016.10.16 —–

## 【BZOJ 2815】[ZJOI2012] 灾难

http://fanhq666.blog.163.com/blog/static/8194342620124274154996/

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000;
const int M = 1000000;

int in[N],sz[N],dep[N],n;
vector<int> G[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void Add_Edge(int u, int v) {
static int T = 0; in[v]++;
}

inline int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x,y);
for (int i=17;~i;i--) {
if (dep[fa[x][i]] >= dep[y]) {
x = fa[x][i];
}
}
if (x == y) return y;
for (int i=17;~i;i--) {
if (fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}

void solve(int w) {
dep[w] = dep[fa[w][0]] + 1;
if (w) G[fa[w][0]].push_back(w);
for (int i=1;i<=17;i++) {
fa[w][i] = fa[fa[w][i-1]][i-1];
}

if (fa[to[i]][0] == -1) {
fa[to[i]][0] = w;
} else {
fa[to[i]][0] = lca(fa[to[i]][0],w);
}

if (--in[to[i]] == 0) {
solve(to[i]);
}
}
}

void Get_Size(int w) {
sz[w] = 1;
for (int i=G[w].size()-1;~i;i--) {
Get_Size(G[w][i]);
sz[w] += sz[G[w][i]];
}
}

int main(){
memset(fa,-1,sizeof(fa));
for (int i=1;i<=n;i++) {
}
if (!in[i]) {