CF600E Lomsat gelral
題目大意
很清楚吧
題解
這是 dsu on tree(中文是啥??)入門題QWQ
首先考慮暴力,很簡單
考慮有技巧的暴力
先輕重鍊剖分
當到樹上的一個節點的時候,
先把輕兒子暴力算一遍,把貢獻删了
然後再把重兒子算一遍, 不用删貢獻,
再把輕兒子的貢獻加到重兒子上面就可以了
時間複雜度為什麼是對的呢???
對于每個節點,他隻可能被它祖先的輕邊周遊到,而一個節點到根最多隻會經過log條輕邊,是以目前節點最多隻會被周遊log次
為什麼一個節點到根最多隻會經過log條輕邊?
考慮對于每個點,它的輕兒子的大小一定小于其他所有兒子的大小的和,是以節點的數量會除以二
同樣,如果目前節點是作為輕兒子,那它往上跳的時候節點數量為至少乘2
是以做多經過log條輕邊
然後代碼實作就很簡單了
#include<bits/stdc++.h>
#define N 100005
using namespace std;
struct edge {
int v, nxt;
}e[N << 1];
int p[N], eid;
void init() {
memset(p, -1, sizeof p);
eid = 0;
}
void insert(int u, int v) {
e[eid].v = v;
e[eid].nxt = p[u];
p[u] = eid ++;
}
int size[N], w[N], cnt[N], col[N], n;
long long MC, CC, ans[N];
void dfs1(int u, int fa) {
size[u] = 1;
for(int i = p[u]; i + 1; i = e[i].nxt) {
int v = e[i].v;
if(v == fa) continue;
dfs1(v, u);
if(size[v] > size[w[u]]) w[u] = v;
size[u] += size[v];
}
}
void calc(int u, int fa, int o, int W) {
cnt[col[u]] += o;
if(cnt[col[u]] == MC) CC += col[u];
if(cnt[col[u]] > MC) MC = cnt[col[u]], CC = col[u];
for(int i = p[u]; i + 1; i = e[i].nxt) {
int v = e[i].v;
if(v == fa || v == W) continue;
calc(v, u, o, W);
}
}
void dfs2(int u, int fa, int o) {
for(int i = p[u]; i + 1; i = e[i].nxt) {
int v = e[i].v;
if(v == fa || v == w[u]) continue;
dfs2(v, u, -1);
}
if(w[u]) dfs2(w[u], u, 1);
calc(u, fa, 1, w[u]);
ans[u] = CC;
if(o == -1) {
calc(u, fa, -1, 0);
MC = 0, CC = 0;
}
}
int main() {
init();
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &col[i]);
for(int i = 1; i < n; i ++) {
int u, v;
scanf("%d%d", &u, &v);
insert(u, v);
insert(v, u);
}
dfs1(1, 0);
dfs2(1, 0, 1);
for(int i = 1; i <= n; i ++) printf("%lld ", ans[i]);
return 0;
}
坑點
long long
感覺沒有啟發式合并 or 線段樹合并好寫啊 QWQ