CF1268E Happy Cactus

https://www.luogu.com.cn/problem/CF1268E

就这还3400？？？

首先考虑一棵树的情况，设一开始$f[i]=1$

把边按边权从大到小插入，假设插入边$(u,v,i)$

显然$f[u]=f[v]=f[u]+f[v]$

考虑仙人掌的情况，先考虑一个环，无非就是链接最小边的时候，最大边两端的会被多算一次，减掉即可

设$g[i]=f[u]+f[v]$

那么就是$f[u]=f[v]=f[u]+f[v]-g[max(C)],g[i]=f[u]+f[v]$
$max(C)$表示当前环上的最大边

code:

	#include
#define N 1000050
using namespace std;
struct edge {int v, nxt, c;
} e[N << 1];
int p[N], eid;
void init() {memset(p, -1, sizeof p);eid = 0;
}
void insert(int u, int v, int c) {e[eid].v = v;e[eid].c = c;e[eid].nxt = p[u];p[u] = eid ++;
}int c[N], gs, sz, col[N], mi[N], ma[N], n, m;
int calc() {if(gs == 1) return 0;    ma[sz] = 0, mi[sz] = m + 1;int x = 0, y = 0;for(int i = 1; i <= gs; i ++) {if(c[i] > ma[sz]) ma[sz] = c[i], x = i;if(c[i] < mi[sz]) mi[sz] = c[i], y = i;}for(int i = 1; i <= gs; i ++) c[i + gs] = c[i];int l = x, r = y;if(l > r) r += gs;for(int i = l; i < r; i ++) if(c[i] < c[i + 1]) return 0;l = x, r = y;if(l < r) l += gs;for(int i = l; i > r; i --) if(c[i] < c[i - 1]) return 0;return 1;    
}
int vis[N], fa[N], a[N], ok[N];
void dfs(int u) {vis[u] = 1;for(int i = p[u]; i + 1; i = e[i].nxt) {int v = e[i].v, w = e[i].c;if(v == fa[u]) continue;if(!vis[v]) {fa[v] = u, a[v] = w;dfs(v);} else if(vis[v] == 2) {gs = 0;++ sz;int x = v;            while(x != u) c[++ gs] = a[x], col[a[x]] = sz, x = fa[x];col[w] = sz; c[++ gs] = w;ok[sz] = calc();}}vis[u] = 2;
}
int f[N], g[N], hau[N], hav[N];
int main() {init();scanf("%d%d", &n, &m);for(int i = 1; i <= m; i ++) {int u, v;scanf("%d%d", &u, &v);insert(u, v, i), insert(v, u, i);hau[i] = u, hav[i] = v;}//printf("114514");dfs(1);for(int i = 1; i <= n; i ++) f[i] = 1;for(int i = m; i >= 1; i --) {int u = hau[i], v = hav[i];g[i] = f[u] = f[v] = f[u] + f[v] - (ok[col[i]] && i == mi[col[i]]) * g[ma[col[i]]];}for(int i = 1; i <= n; i ++) printf("%d ", f[i] - 1);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！