因为洛谷的remote CodeForces Judge 挂了，先把一些过了的 CF 题的 AC-code 放在此处
\(\small \textcolor{blue}{CF280C}\)
\(\small \textcolor{purple}{CF911G}\)
\(\small \textcolor{blue} {CF865D}\)
\(\small \textcolor{purple}{CF960H}\)
\(\small \textcolor{purple}{CF79D}\)
\(\small \textcolor{purple}{CF786B}\)
\(\small \textcolor{green}{CF988D}\)
\(\small \textcolor{blue}{CF508D}\)
\(\small \textcolor{purple}{CF613D}\)
\(\small \textcolor{purple}{CF1209E2}\)
\(\small \textcolor{blue}{CF165E}\)
\(\small\textcolor{purple}{CF718C}\)
\(\small\textcolor{purple}{CF1009F}\)
#include<bits/stdc++.h>
using namespace std;
int rd() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
void wt(int x) {
static int sta[35];
int f = 1;
if(x < 0) f = -1,x *= f;
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
if(f == -1) putchar('-');
while (top) putchar(sta[--top] + 48);
}
const int N = 1e6+5;
int n,dep[N],a[N];
int head[N],nxt[N<<1],to[N<<1],cnt;
void init() {memset(head,-1,sizeof(head));cnt = 0;}
void add(int u,int v) {
nxt[cnt] = head[u];
to[cnt] = v;
head[u] = cnt++;
}
int rt[N];
namespace sgt{
int mx[N * 25],ls[N * 25],rs[N * 25],tot;
#define mid ((pl + pr) >> 1)
void push_up(int p) {mx[p] = max(mx[ls[p]],mx[rs[p]]);}
void update(int &p,int pl,int pr,int k) {
if(!p) p = ++tot;
if(pl == pr) {mx[p]++;return;}
if(k <= mid) update(ls[p],pl,mid,k);
else update(rs[p],mid+1,pr,k);
push_up(p);
}
int query(int p,int pl,int pr) {
if(!p) return 0;
if(pl == pr) return pl;
if(mx[ls[p]] >= mx[rs[p]]) return query(ls[p],pl,mid);
else return query(rs[p],mid + 1,pr);
}
int merge(int x,int y,int pl,int pr) {
if(!x || !y) return x + y;
if(pl == pr) {
mx[x] += mx[y];
return x;
}
ls[x] = merge(ls[x],ls[y],pl,mid);
rs[x] = merge(rs[x],rs[y],mid+1,pr);
push_up(x);
return x;
}
}
void dfs(int x,int f) {
dep[x] = dep[f] + 1;
for(int i = head[x];~i;i = nxt[i]) {
int y = to[i];
if(y ^ f) {
dfs(y,x);
rt[x] = sgt::merge(rt[x],rt[y],1,n);
}
}
sgt::update(rt[x],1,n,dep[x]);
a[x] = sgt::query(rt[x],1,n) - dep[x];
}
signed main() {
init();
n = rd();
for(int i = 1;i<n;i++) {
int u = rd(),v = rd();
add(u,v);add(v,u);
}
dfs(1,0);
for(int i = 1;i<=n;i++) wt(a[i]),putchar('\n');
return 0;
}
\(\small\textcolor{blue}{CF609E}\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
int rd() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
void wt(int x) {
static int sta[35];
int f = 1;
if(x < 0) f = -1,x *= f;
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
if(f == -1) putchar('-');
while (top) putchar(sta[--top] + 48);
}
const int M = 2e5+5,N = M,inf = 0x3f3f3f3f3f3f3f3fLL;
int n,m,ans,det[M],s[N];
array<int,4> e[M];
bool vis[N];
int head[N],nxt[N<<1],to[N<<1],cnt,val[N<<1];
void init() {memset(head,-1,sizeof(head));cnt = 0;}
void add(int u,int v,int w) {
nxt[cnt] = head[u];
to[cnt] = v;
val[cnt] = w;
head[u] = cnt++;
}
int find(int x) {
if(s[x] ^ x) s[x] = find(s[x]);
return s[x];
}
void kruskal() {
for(int i = 1;i<=n;i++) s[i] = i;
int tot = 0;
for(int i = 1;i<=m;i++) {
int fx = find(e[i][1]),fy = find(e[i][2]);
if(fx ^ fy) {
s[fx] = fy;
vis[e[i][3]] = true;
add(e[i][1],e[i][2],e[i][0]);
add(e[i][2],e[i][1],e[i][0]);
ans += e[i][0];
tot++;
if(tot == n - 1) break;
}
}
}
int dep[N],fa[N],siz[N],son[N],id[N],w[N],_w[N],top[N],num;
void dfs1(int x,int f) {
fa[x] = f;
siz[x] = 1;
dep[x] = dep[f] + 1;
for(int i = head[x];~i;i = nxt[i]) {
int y = to[i];
if(y ^ f) {
dfs1(y,x);
w[y] = val[i];
siz[x] += siz[y];
if(siz[son[x]] < siz[y]) son[x] = y;
}
}
}
void dfs2(int x,int topx) {
top[x] = topx;
id[x] = ++num;
_w[num] = w[x];
if(!son[x]) return;
dfs2(son[x],topx);
for(int i = head[x];~i;i = nxt[i]) {
int y = to[i];
if(y ^ fa[x] && y ^ son[x]) dfs2(y,y);
}
}
namespace sgt{
#define ls (p << 1)
#define rs (ls | 1)
#define mid ((pl + pr) >> 1)
int mx[N<<2];
void push_up(int p) {
mx[p] = max(mx[ls],mx[rs]);
}
void build(int p,int pl,int pr) {
if(pl == pr) {
mx[p] = _w[pl];
return;
}
build(ls,pl,mid);
build(rs,mid+1,pr);
push_up(p);
}
int query(int p,int pl,int pr,int l,int r) {
if(l > r) return 0;
if(l <= pl && pr <= r) return mx[p];
if(r <= mid) return query(ls,pl,mid,l,r);
else if(l > mid) return query(rs,mid+1,pr,l,r);
else return max(query(ls,pl,mid,l,r),query(rs,mid+1,pr,l,r));
}
}
int query(int x,int y) {
int re = 0;
while(top[x] ^ top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x,y);
re = max(re,sgt::query(1,1,n,id[top[x]],id[x]));
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x,y);
re = max(re,sgt::query(1,1,n,id[x] + 1,id[y]));
return re;
}
int a[N];
signed main() {
init();
n = rd(),m = rd();
for(int i = 1;i<=m;i++)
e[i][1] = rd(),e[i][2] = rd(),e[i][0] = rd(),e[i][3] = i;
sort(e + 1,e + m + 1);
kruskal();
dfs1(1,0),dfs2(1,1);
sgt::build(1,1,n);
for(int i = 1;i<=m;i++) {
if(vis[e[i][3]]) a[e[i][3]] = ans;
else {
int re = query(e[i][1],e[i][2]);
a[e[i][3]] = ans + e[i][0] - re;
}
}
for(int i = 1;i<=m;i++) wt(a[i]),putchar('\n');
return 0;
}