Submission #49506487

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair<int, int> PII;
const int MAXN = 212345;
const int inf = 1123456789;
//const ll inf = 1000000000000000018ll;
const LL mod = 998244353;
#define rep(i, l, r) for (int i=(l); i<=(r); i++)
#define per(i, r, l) for (int i=(r); i>=(l); i--)
#define mem(a, b) memset(a, b, sizeof(a))

int N, in[MAXN], out[MAXN], clk;
vector<int> nxt[MAXN];
LL ansn[MAXN];

int rt[MAXN];
struct segmentTree {
	#define lson ls[x]
	#define rson rs[x]
	int tot, cnt[MAXN<<5], ls[MAXN<<5], rs[MAXN<<5];
	segmentTree() {
        tot = 0, mem(cnt, 0), mem(ls, 0), mem(rs, 0);
	}
    void pushup(int x) { cnt[x] = cnt[lson] + cnt[rson]; }
	void update(int &x, int l, int r, int p) {
		if (!x) x = ++tot;
		if (l==r) cnt[x] = 1;
        else {
			int mid = (l + r) >> 1;
			if (mid>=p) update(lson, l, mid, p);
			if (mid< p) update(rson, mid+1, r, p);
			pushup(x);
		}
	}
    int query(int x, int l, int r, int p) { // <=p
        if (!x) return 0;
        if (r<=p) return cnt[x];
        else {
            int mid = (l + r) >> 1;
            if (mid>=p) return query(lson, l, mid, p);
            else return cnt[lson] + query(rson, mid+1, r, p);
        }
    }
	int merge(int x, int y, int l, int r) {
		if (!x) return y;
		if (!y) return x;
		if (l==r) {
			cnt[x] += cnt[y];
			return x;
		} else {
			int mid = (l + r) >> 1;
			ls[x] = merge(ls[x], ls[y], l, mid);
			rs[x] = merge(rs[x], rs[y], mid+1, r);
			pushup(x);
			return x;
		}
	}
} ST;

void dfs1(int x, int f)
{
    in[x] = ++clk;
    for (auto v: nxt[x]) if (v!=f) dfs1(v, x);
    out[x] = clk;
}
void dfs2(int x, int f)
{
    ST.update(rt[x], 1, N, x);
    int sumk = 0;
    for (auto v: nxt[x]) if (v!=f) {
        dfs2(v, x);
        int k = ST.query(rt[v], 1, N, x);
        ansn[1] += k;
        ansn[in[v]] -= k;
        ansn[out[v]+1] += k;
        sumk += k;
        ST.merge(rt[x], rt[v], 1, N);
    }
    ansn[in[x]] += x-1-sumk;
    ansn[out[x]+1] -= x-1-sumk;
}
int main()
{
    scanf("%d", &N);
    rep(i, 2, N) {
        int a, b; scanf("%d%d", &a, &b);
        nxt[a].push_back(b), nxt[b].push_back(a);
    }
    dfs1(1, 0);
    for (int i=1; i<=N; i++) rt[i] = i; ST.tot = N;
    dfs2(1, 0);
    rep(i, 1, N) ansn[i] += ansn[i-1];
    rep(i, 1, N) printf("%lld ", ansn[in[i]]);
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:93:5: warning: this ‘for’ clause does not guard... [-Wmisleading-indentation]
   93 |     for (int i=1; i<=N; i++) rt[i] = i; ST.tot = N;
      |     ^~~
Main.cpp:93:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘for’
   93 |     for (int i=1; i<=N; i++) rt[i] = i; ST.tot = N;
      |                                         ^~
Main.cpp:87:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   87 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
Main.cpp:89:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   89 |         int a, b; scanf("%d%d", &a, &b);
      |                   ~~~~~^~~~~~~~~~~~~~~~

Judge Result