线段树合并WA0求调
查看原帖
线段树合并WA0求调
770611
xxxxxzy楼主2023/10/13 15:42
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m,fat[100005],x[100005], y[100005], z[100005], p, d[100005], t, f[200005][22], tot, root[100005];
vector<int> ed[100005];
map<int, int> cnt;
int to[100005];
void dfsn(int x,int fa){
	fat[x]=fa;
	for(int i=0;i<ed[x].size();i++){
		int y=ed[x][i];
		if(y==fa) continue;
		dfsn(y,x);
	}
}
struct segmentTree {
    int lc, rc, maxn, dat, mx, x;
}tt[1000005];
int build() {
    tt[++tot].lc = tt[tot].rc = tt[tot].dat = 0;
    return tot;
}
void add(int p, int l, int r, int k, int d) {
    if (l == r) {
        tt[p].dat += d;
        tt[p].mx = l;
        return;
    }
    int mid = (l + r) >> 1;
    if (k <= mid) {
        if (!tt[p].lc)
            tt[p].lc = build();
        add(tt[p].lc, l, mid, k, d);
    } else {
        if (!tt[p].rc)
            tt[p].rc = build();
        add(tt[p].rc, mid + 1, r, k, d);
    }
    if (tt[tt[p].lc].dat >= tt[tt[p].rc].dat)
        tt[p].mx = tt[tt[p].lc].mx;
    else
        tt[p].mx = tt[tt[p].rc].mx;
    tt[p].dat = max(tt[tt[p].lc].dat, tt[tt[p].rc].dat);
}
int merge(int p, int q, int l, int r) {
    if (!p)
        return q;
    if (!q)
        return p;
    if (l == r) {
        tt[p].dat += tt[q].dat;
        tt[p].mx = l;
        return p;
    }
    int mid = (l + r) >> 1;
    tt[p].lc = merge(tt[p].lc, tt[q].lc, l, mid);
    tt[p].rc = merge(tt[p].rc, tt[q].rc, mid + 1, r);
    if (tt[tt[p].lc].dat >= tt[tt[p].rc].dat)
        tt[p].mx = tt[tt[p].lc].mx;
    else
        tt[p].mx = tt[tt[p].rc].mx;
    tt[p].dat = max(tt[tt[p].lc].dat, tt[tt[p].rc].dat);
    return p;
}
void bfs() {
    queue<int> q;
    q.push(1);
    d[1] = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < ed[x].size(); i++) {
            int y = ed[x][i];
            if (d[y])
                continue;
            d[y] = d[x] + 1;
            f[y][0]=x;
            for (int j = 1; j <= t; j++) {
                f[y][j] = f[f[y][j - 1]][j - 1];
            }
            q.push(y);
        }
    }
}
int lca(int x, int y) {
    if (d[x] > d[y])
        swap(x, y);
    for (int i = t; i >= 0; i--) {
        if (d[f[y][i]] >= d[x])
            y = f[y][i];
    }
    if (x == y)
        return x;
    for (int i = t; i >= 0; i--) {
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    }
    return f[x][0];
}
int ans[100005];
void dfs(int x, int fa) {
    for (int i = 0; i < ed[x].size(); i++) {
        int y = ed[x][i];
        if (y == fa)
            continue;
        dfs(y, x);
        merge(x, y, 1, p);
    }
    ans[x] = to[tt[root[x]].mx];
}
struct query{
	int x,y,z;
}op[100005];
bool cmp(query a,query b){
	return a.z<b.z;
}
signed main() {
    cin >> n >> m;
    t = (int)(log(n) / log(2)) + 1;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        ed[u].push_back(v);
        ed[v].push_back(u);
    }
    bfs();
    dfsn(1,0);
    for (int i = 1; i <= m; i++) cin >>op[i].x>>op[i].y>>op[i].z;
    sort(op+1,op+1+m,cmp);
    for(int i=1;i<=m;i++){
    	if (!cnt[op[i].z])
       		cnt[op[i].z] = ++p, to[p] = op[i].z;
		op[i].z = cnt[op[i].z];
	}
//	for(int i=1;i<=p;i++) cout<<i<<" "<<to[i]<<endl;
    for (int i = 1; i <= n; i++) root[i] = build();
    for (int i = 1; i <= m; i++) {
        add(root[op[i].x], 1, p, op[i].z, 1);
        add(root[op[i].y], 1, p, op[i].z, 1);
        add(root[lca(op[i].x, op[i].y)], 1, p, op[i].z, -1);
        add(root[fat[lca(op[i].x, op[i].y)]], 1, p, op[i].z, -1);
//        cout<<op[i].x<<" "<<op[i].y<<" "<<lca(op[i].x, op[i].y)<<endl;
    }
    dfs(1, -1);
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << endl;
    }
}

2023/10/13 15:42
加载中...