[Codeforces] 375D - Tree and Queries

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 375D - Tree and Queries
Source            : Codeforces
Category          : Graph Theory
Algorithm         : DSU on Tree
Verdict           : Accepted 

#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 1e5 + 5;
 
struct info
{
    int k, id;
    info(int k = 0, int id = 0) : k(k), id(id) {}
};
 
vector <int> graph[maxn];
vector <info> query[maxn];
int color[maxn];
int cnt[maxn], fre[maxn], ans[maxn];  // frequency of color in subtree of v
int subtreeSize[maxn], big[maxn];
 
void dfs(int u = 1, int p = -1)
{
    subtreeSize[u] = 1;
    for (int v : graph[u])
    {
        if (v == p) continue;
        dfs(v, u);
        subtreeSize[u] += subtreeSize[v];
    }
}
 
void add(int u, int p)
{
    cnt[ color[u] ]++;
    fre[ cnt[color[u] ] ]++;
    for (int v : graph[u])
    {
        if (v == p || big[v]) continue;
        add(v, u);
    }
}
 
void remov(int u, int p)
{
    fre[ cnt[ color[u] ] ]--;
    cnt[ color[u] ]--;
    for (int v : graph[u])
    {
        if (v == p || big[v]) continue;
        remov(v, u);
    }
}
 
void dsu(int u = 1, int p = -1, bool keep = 0)
{
    int mx = -1, bigChild = -1;
    for (auto v : graph[u])
    {
        if (v == p) continue;
        if (subtreeSize[v] > mx) mx = subtreeSize[v], bigChild = v;
    }
    for (int v : graph[u])
    {
        if (v == p || v == bigChild) continue;
        dsu(v, u, 0);
    }
    if (bigChild != -1) dsu(bigChild, u, 1), big[bigChild] = 1;
    add(u, p);
    // --- answer the query of subtree u
    for (info it : query[u]) ans[it.id] = fre[it.k];
    if (bigChild != -1) big[bigChild] = 0;
    if (keep == 0) remov(u, p);
}
 
int main()
{
    int tnode, tquery;
    scanf("%d %d", &tnode, &tquery);
    for (int i = 1; i <= tnode; i++) scanf("%d", &color[i]);
    for (int e = 1; e < tnode; e++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u].emplace_back(v);
        graph[v].emplace_back(u);
    }
    for (int i = 1; i <= tquery; i++)
    {
        int v, k;
        scanf("%d %d", &v, &k);
        query[v].emplace_back(k, i);
    }
    dfs();
    dsu();
    for (int i = 1; i <= tquery; i++) printf("%d\n", ans[i]);
}

[UVa] 13164 - Performance Review

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13164 - Performance Review
Source            : UVa Online Judge
Category          : Graph Theory, Data Structure
Algorithm         : DSU on Tree, Binary Indexed Tree
Verdict           : Accepted 

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll              long long
 
static const int maxn = 2e5 + 5;
 
ll tree[maxn];
int N; // N = max rank
 
vector <int> graph[maxn];
int rnk[maxn], tim[maxn];
int subtreeSize[maxn];
ll ans[maxn];
bool big[maxn];
 
inline void update(int pos, int val)
{
      while (pos <= N)
      {
            tree[pos] += val;
            pos += pos & (-pos);
      }
}
 
inline ll read(int pos)
{
      ll sum = 0;
      while (pos > 0)
      {
            sum += tree[pos];
            pos -= pos & (-pos);
      }
      return sum;
}
 
inline void dfs(int u, int p = -1)
{
      subtreeSize[u] = 1;
      for (int v : graph[u])
      {
            if (v == p) continue;
            dfs(v, u);
            subtreeSize[u] += subtreeSize[v];
      }
}
 
inline void add(int u, int p)
{
      update(rnk[u], tim[u]);
      for (int v : graph[u])
      {
            if (v == p || big[v]) continue;
            add(v, u);
      }
}
 
inline void remov(int u, int p)
{
      update(rnk[u], -tim[u]);
      for (int v : graph[u])
      {
            if (v == p || big[v]) continue;
            remov(v, u);
      }
}
 
inline ll getTime(int u)
{
      return read(rnk[u] - 1);
}
 
inline void dsu(int u, int p, bool keep)
{
      int mx = -1;
      int bigChild = -1;
      for (int v : graph[u])
      {
            if (v == p) continue;
            if (subtreeSize[v] > mx) mx = subtreeSize[v], bigChild = v;
      }
      for (int v : graph[u])
      {
            if (v == p || v == bigChild) continue;
            dsu(v, u, 0);
      }
      if (bigChild != -1) dsu(bigChild, u, 1), big[bigChild] = 1;
      add(u, p);
      ans[u] = getTime(u);
      if (bigChild != -1) big[bigChild] = 0;
      if (keep == 0) remov(u, p);
}
 
inline void clean()
{
      for (int i = 0; i < maxn; i++)
      {
            graph[i].clear();
            rnk[i] = 0;
            tim[i] = 0;
            tree[i] = 0;
            big[i] = 0;
            subtreeSize[i] = 0;
            ans[i] = 0;
      }
}
 
int main()
{
      int tnode;
      while (cin >> tnode)
      {
            int m, r, t;
            int root = -1;
            N = 0;
            for (int i = 1; i <= tnode; i++)
            {
                  cin >> m >> r >> t;
                  rnk[i] = r;
                  tim[i] = t;
                  if (r > N) N = r;
                  if (m == -1) root = i;
                  if (m != -1)
                  {
                        graph[i].push_back(m);
                        graph[m].push_back(i);
                  }
            }
            dfs(root, -1);
            dsu(root, -1, 0);
            for (int i = 1; i <= tnode; i++) cout << ans[i] << endl;
            clean();
      }
}
 

[Codeforces] E. Lomsat gelral

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Lomsat gelral
Source            : Codeforces
Category          : Graph Theory
Algorithm         : DSU on Tree
Verdict           : Accepted

#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
 
using namespace std;
using namespace __gnu_pbds;
 
#define ll            long long
#define eb            emplace_back
 
static const int maxn = 2e5 + 5;
 
template <typename T> using orderSet = tree <T, null_type, greater <T>, rb_tree_tag, tree_order_statistics_node_update>;
 
orderSet <ll> X;
vector <int> graph[maxn];
ll color[maxn], sizeSubTree[maxn], cnt[maxn];
bool big[maxn];
ll ans[maxn];
ll occSum[maxn];
 
void dfs(int u = 1, int p = -1)
{
    sizeSubTree[u] = 1;
    for (int v : graph[u])
    {
        if (v == p) continue;
        dfs(v, u);
        sizeSubTree[u] += sizeSubTree[v];
    }
}
 
void Add(ll num)
{
    X.insert(num);
}
 
void Erase(ll num)
{
    X.erase(X.lower_bound(num));
}
 
void update(int u, int p, ll x)
{
    // first erase the previous color
    Erase(cnt[ color[u] ]);
    occSum[ cnt[ color[u] ] ] -= color[u];
    // increment color size
    cnt[ color[u] ] += x;
    // Add to ordered set
    Add(cnt[ color[u] ]);
    occSum[ cnt[ color[u] ] ] += color[u];
 
    for (int v : graph[u])
    {
        if (v == p || big[v]) continue;
        update(v, u, x);
    }
}
 
ll getResult(int u)
{
    int f = *X.find_by_order(0);
    return occSum[f];
}
 
void dsu(int u = 1, int p = -1, bool keep = 0)
{
    int mx = -1, bigChild = -1;
    for (int v : graph[u])
    {
        if (v == p) continue;
        if (sizeSubTree[v] > mx) mx = sizeSubTree[v], bigChild = v;
    }
    for (int v : graph[u])
    {
        if (v == p || v == bigChild) continue;
        dsu(v, u, 0); // Run a dfs from small child and clear them from cnt
    }
    if (bigChild != -1)
    {
        dsu(bigChild, u, 1);
        big[bigChild] = 1; // bigchild marked as big and not cleared from cnt
    }
    update(u, p, 1);
    ans[u] = getResult(u);
    if (bigChild != -1) big[bigChild] = 0;
    if (keep == 0) update(u, p, -1);
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    int tnode;
    scanf("%d", &tnode);
    for (int i = 1; i <= tnode; i++) scanf("%lld", color+i);
    for (int e = 1; e < tnode; e++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u].eb(v);
        graph[v].eb(u);
    }
    dfs();
    dsu();
    for (int i = 1; i <= tnode; i++) printf("%lld ", ans[i]);
}
 

[toph.co] Sabiha and the War Victims

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Sabiha and the War Victims
Source            : toph.co
Category          : Graph Theory
Algorithm         : DSU on Tree
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll                 long long
#define MOD                1000000007
 
static const int MAXN = 2e5 + 5;
 
vector <int> graph[MAXN];
bool big[MAXN];
int sz[MAXN], tshirt[MAXN], temp[MAXN], cnt[MAXN];
int odd;
ll fact[MAXN], ifact[MAXN], up, down;
ll ans[MAXN];
 
map <int, int> mapper;
 
ll modPow(ll a, ll b, ll m)
{
    if (b == 1) return a % m;
    if (b & 1) return (a % m * modPow(a, b-1, m) % m) % m;
    ll ret = modPow(a, b>>1, m);
    return (ret % m * ret % m) % m;
}
 
ll modInv(ll a, ll m)
{
    return modPow(a, m-2, m);
}
 
void factorial()
{
    fact[0] = 1;
    ifact[0] = 1;
    for (int i = 1; i < MAXN; i++)
    {
        fact[i] = (i * fact[i-1]) %MOD;
        ifact[i] = modInv(fact[i], MOD);
    }
}
 
void dfs1(int u, int p=-1)
{
    sz[u] = 1;
    int len = graph[u].size();
    for (int i = 0; i < len; i++)
    {
        int v = graph[u][i];
        if (v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v];
    }
}
 
void add(int u, int p, int x)
{
    int c = tshirt[u];
    !(cnt[c] & 1) ? odd++ : odd--;
    up -= cnt[c];
    down = (down * ifact[cnt[c]>>1]) %MOD;
    cnt[c] += x;
    up += cnt[c];
    down = (down * fact[cnt[c]>>1]) %MOD;
    int len = graph[u].size();
    for (int i = 0; i < len; i++)
    {
        int v = graph[u][i];
        if (v == p || big[v]) continue;
        add(v, u, x);
    }
}
 
void remov(int u, int p, int x)
{
    int c = tshirt[u];
    cnt[c] & 1 ? odd-- : odd++;
    up -= cnt[c];
    down = (down * ifact[cnt[c]>>1]) %MOD;
    cnt[c] -= x;
    up += cnt[c];
    down = (down * fact[cnt[c]>>1]) %MOD;
    int len = graph[u].size();
    for (int i = 0; i < len; i++)
    {
        int v = graph[u][i];
        if (v == p || big[v]) continue;
        remov(v, u, x);
    }
}
 
void dfs(int u, int p, int keep)
{
    int mx(-1), bigChild(-1);
    int len = graph[u].size();
    for (int i = 0; i < len; i++)
    {
        int v = graph[u][i];
        if (v == p) continue;
        if (sz[v] > mx) mx = sz[v], bigChild = v;
    }
    for (int i = 0; i < len; i++)
    {
        int v = graph[u][i];
        if (v == p || bigChild == v) continue;
        dfs(v, u, 0);
    }
    if (bigChild != -1) dfs(bigChild, u, 1), big[bigChild] = 1;
    add(u, p, 1);
    ll res = 0;
    if (odd <= 1)
    {
        res = (fact[up>>1] * modInv(down, MOD)) %MOD;
    }
    ans[u] = res;
    if (bigChild != -1) big[bigChild] = 0;
    if (keep == 0) remov(u, p, 1);
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    factorial();
    up = 0;
    down = 1;
 
    int tNode;
    scanf("%d", &tNode);
    for (int i = 1; i <= tNode; i++)
    {
        scanf("%d", tshirt+i);
        temp[i] = tshirt[i];
    }
    sort(temp+1, temp+tNode+1);
    int id = 0;
    for (int i = 1; i <= tNode; i++)
    {
        int x = temp[i];
        if (mapper.count(x) == 0)
        {
            id++;
            mapper[x] = id;
        }
    }
    for (int i = 1; i <= tNode; i++)
    {
        tshirt[i] = mapper[tshirt[i]];
    }
    for (int edge = 1; edge < tNode; edge++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs1(1);
    dfs(1, -1, 0);
    for (int i = 1; i <= tNode; i++)
    {
        printf("%lld", ans[i]);
        printf(i==tNode ? "\n" : " ");
    }
}