10 pts 求助!悬关
查看原帖
10 pts 求助!悬关
1296826
lcfollower楼主2024/7/14 20:18

rt。

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

#define db double
#define inf 0x3f3f3f3f
#define infi 0x3f3f3f3f3f3f3f3fll
#define _Dark_Star exit(0)
#define up(i,x,y) for(register int i=x;i<=y;++i)
#define dn(i,x,y) for(register int i=x;i>=y;--i)
#define max(a,b) a > b ? a : b

using namespace std;

inline int read(){int x=0;bool f=0;char ch=getchar();while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return (f?-x:x);}
inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10|48);}
inline void writeln(int x){write(x),putchar('\n');}
inline void writesp(int x){write(x),putchar(' ');}
const int N = 1e5 + 10 ,M = N * 80;
struct Edge{
  int to ,nxt;
}edge[M << 1]; int head[N];
int n , m, cnt;
int fa[N][21], dep[N] , lg[N] ,sum[M], mx[M], ls[M], rs[M] ,ans[N], root[N];

inline void add(int u,int v){edge[++cnt] = {v ,head[u]} ,head[u] = cnt;}
inline void dfs(int u,int fath){
  dep[u] = dep[fath] + 1 ,fa[u][0] = fath;
  up(i,1,20) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for(int i = head[u]; ~i ; i = edge[i].nxt){
    int v = edge[i].to;
    if(v != fath) dfs(v ,u);
  }
} inline int LCA(int u,int v){
  if(dep[u] > dep[v]) swap(u ,v);
  while(dep[u] > dep[v]) u = fa[u][lg[dep[u] - dep[v]]];
  if(u == v) return u;
  dn(i ,lg[dep[u]] ,0) if(fa[u][i] != fa[v][i]) u = fa[u][i] ,v = fa[v][i];
  return fa[u][0];
} inline void pushup(int u){
  if(sum[ls[u]] >= sum[rs[u]]) sum[u] = sum[ls[u]] ,mx[u] = mx[ls[u]];
  else sum[u] = sum[rs[u]] ,mx[u] = mx[rs[u]];
} inline void update(int &rt ,int l,int r,int z,int val){
  if(!rt) rt = ++ cnt;
  if(l == r){sum[rt] += val ,mx[rt] = z;return;}
  int mid = ((l + r) >> 1);
  if(z <= mid) update(ls[rt] ,l ,mid, z, val);
  else update(rs[rt] ,mid + 1 ,r ,z ,val);
  pushup(rt);
} inline int merge(int u,int v,int l,int r){
  if(!u || !v) return u | v;
  if(l == r){sum[u] += sum[v] ; return u;}
  int mid = ((l + r) >> 1);
  ls[u] = merge(ls[u] ,ls[v] , l ,mid);
  rs[u] = merge(rs[u] ,rs[v] ,mid + 1, r);
  pushup(u);
  return u;
} inline void dfs2(int u,int fa){
  for(int i = head[u]; ~i ;i = edge[i].nxt){
    int v = edge[i].to;
    if(v == fa) continue;
    dfs2(v ,u);
    root[u] = merge(root[u] ,root[v] ,1 ,N);
  }
  ans[u] = mx[root[u]];
  if(!sum[root[u]]) ans[u] = 0;
} signed main(){
  memset(head, -1 ,sizeof head);
  n = read() ,m = read();
  lg[0] = -1;
  up(i,1,n) lg[i] = lg[i >> 1] + 1;
  up(i,1,n - 1){int u = read() ,v = read();add(u ,v) ,add(v ,u);}
  dfs(1 ,0);
  while(m --){
    int u = read() ,v = read() ,w = read();
    int lca = LCA(u ,v);
    update(root[u] ,1, N ,w ,1);
    update(root[v] ,1, N ,w, 1);
    update(root[lca] ,1, N, w , -1);
    update(root[fa[lca][0]] , 1 ,N ,w, -1);
  }
  dfs2(1 ,0);
  up(i,1,n) writeln(ans[i]);
  return 0;
}
2024/7/14 20:18
加载中...