Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define MAXN 70100
- #define K 300
- #define INF 2100000000LL
- #define MAXBLOCKS 300
- //#define int long long
- typedef long long LL;
- int N;
- vector<int> adj[MAXN];
- //leafdist
- int L[MAXN], D[MAXN];
- int cnt = 0;
- bool vis[MAXN];
- int in[MAXN], out[MAXN];
- void leafDfs(int n, int p=0){
- D[n] = D[p] + 1;
- if(!vis[n]){
- vis[n] = true;
- in[n] = cnt;
- cnt++;
- }
- for(int v : adj[n])
- if(v != p){
- leafDfs(v, n);
- L[n] = min(L[n], L[v] + 1);
- }
- out[n] = cnt;
- }
- void leafDfs2(int n, int p=0){
- L[n] = min(L[n], L[p] + 1);
- for(int v : adj[n])
- if(v != p)
- leafDfs2(v, n);
- }
- //BIT stuff
- int BIT[MAXBLOCKS][2*MAXN];
- int ans[MAXN];
- void add(int i, int val, int block){
- for(i+=N; i < 2*MAXN; i += (i & -i))
- BIT[block][i] += val;
- }
- LL get(int i, int block){
- LL ret = 0;
- for(i+=N; i > 0; i -= (i & -i))
- ret += BIT[block][i];
- return ret;
- }
- //answer dfs
- int key[MAXN];
- int val[MAXN];
- int lazy[MAXBLOCKS];
- int overall_lazy;
- inline void resetTable(int x){
- for(int i = x*K; i < min(N, x*K+K); i++)
- add(key[i], -val[i], x);
- }
- inline void createTable(int x){
- for(int i = x*K; i < min(N, x*K+K); i++)
- add(key[i], val[i], x);
- }
- inline void addDepths(int l, int r, int val){
- for(int i = l; i <= r; i++)
- key[i] += val;
- }
- inline void update(int l, int r, int val){
- int ls = l / K;
- int rs = r / K;
- //reset table, update D, refill
- if(ls == rs){
- resetTable(ls);
- addDepths(l, r, val);
- createTable(ls);
- }
- else{
- // return;
- //left
- resetTable(ls);
- addDepths(l, ls*K+K, val);
- createTable(ls);
- //middle
- for(int i = ls + 1; i < rs; i++)
- lazy[i] += val;
- //right
- resetTable(rs);
- addDepths(rs*K, r, val);
- createTable(rs);
- }
- }
- inline void dfs(int n, int p){
- //calculate answer for this node
- for(int i = 0; i <= N / K; i++)
- ans[n] += get(-lazy[i]-overall_lazy, i);
- for(int v : adj[n]){
- if(v != p){
- overall_lazy--;
- update(in[v], out[v]-1, 2);
- dfs(v, n);
- overall_lazy++;
- update(in[v], out[v]-1, -2);
- }
- }
- }
- int main() {
- freopen("atlarge.in", "r", stdin); freopen("atlarge.out", "w", stdout);
- cin >> N;
- //K = sqrt(N); // the size of each block
- for(int i = 0; i < N-1; i++){
- int a, b;
- cin >> a >> b;
- adj[a].push_back(b);
- adj[b].push_back(a);
- }
- //calculate leafdist, dfs order, and depths
- for(int i = 0; i <= N; i++){
- if(adj[i].size() == 1)
- L[i] = 0;
- else
- L[i] = INF;
- }
- D[0] = -1;
- leafDfs(1);
- leafDfs2(1);
- for(int i = 1; i <= N; i++){
- key[in[i]] = L[i] - D[i];
- val[in[i]] = 2 - (int)adj[i].size();
- }
- //initialize the BIT tables
- for(int i = 0; i <= N / K; i++)
- createTable(i);
- //dfs from node 1, update BITs as you go
- dfs(1, 0);
- for(int i = 1; i <= N; i++) {
- if(adj[i].size() == 1)
- cout << 1 << endl;
- else
- cout << ans[i] << endl;
- }
- // cout << 3 << endl << 1 << endl << 3 << endl << 3 << endl << 3 << endl << 1 << endl << 1;
- // cout << endl;
- // for(int i = 1; i <= N; i++)
- // cout << setw(3) << i;
- // cout << endl;
- // for(int i = 1; i <= N; i++)
- // cout << setw(3) << in[i];
- // cout << endl;
- // for(int i = 0; i < N; i++)
- // cout << setw(3) << rin[i];
- // cout << endl;
- // cout << "K: " << K << endl;
- // for(int i = 1; i <= N; i++)
- // cout << setw(3) << L[i] - D[i];
- // cout << endl;
- // for(int i = 1; i <= N; i++)
- // cout << setw(3) << 2-(int)adj[i].size();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement