CSES. Road Reparation

1.Problem

https://cses.fi/problemset/task/1675

2.Idea

Standard MST with UnionFind implementation

3.Source

 int n, m;  
 struct Edge {  
      int u, v, c;  
      bool operator < (const Edge &a)const {  
           return c < a.c;  
      }  
 } Edges[N];  
 struct UF {  
      vector<int> Parent;  
      vector<int> Size;  
      int Count;  
      void init(int n) {  
           Count = n;  
           Parent.resize(n);  
           Size.resize(n);  
           REP(i, n) {  
                make_set(i);  
           }  
      }  
      void make_set(int v) {  
           Parent[v] = v;  
           Size[v] = 1;  
      }  
      int find_set(int v) {  
           if (v == Parent[v])  
                return v;  
           return Parent[v] = find_set(Parent[v]);  
      }  
      void union_sets(int a, int b) {  
           a = find_set(a);  
           b = find_set(b);  
           if (a != b) {  
                if (Size[a] < Size[b])  
                     swap(a, b);  
                Count--;  
                Parent[b] = a;  
                Size[a] += Size[b];  
           }  
      }  
 };  
 void solve()  
 {  
      cin >> n >> m;  
      REP(i, m) {  
           cin >> Edges[i].u >> Edges[i].v >> Edges[i].c;  
           Edges[i].u--;  
           Edges[i].v--;  
      }  
      sort(Edges, Edges + m);  
      UF uf;  
      uf.init(n);  
      Int ret = 0;  
      REP(i, m) {  
           int u = Edges[i].u;  
           int v = Edges[i].v;  
           int c = Edges[i].c;  
           if (uf.find_set(u) != uf.find_set(v)) {  
                ret += c;  
                uf.union_sets(u, v);  
           }  
      }  
      if (uf.Count == 1) cout << ret << endl;  
      else cout << "IMPOSSIBLE" << endl;  
 }  

POJ.3214 Heap

1.Problem
http://poj.org/problem?id=3214

2.Idea
Post-Order traversal and LIS.

3.Source

 #include<iostream>  
 #include<cstdio>  
 #include<algorithm>  
 #include<queue>  
 #define maxn 0x7fffffff  
 using namespace std;  
 const int N=2e6;  
 int a[N];  
 int n,x=0;  
 int st[N];  
 vector<int>v;  
 void solve(int k,int& d){  
   if(2*k<=x) solve(k<<1,d);  
   if(2*k+1<=x) solve((k<<1)+1,++d);  
   v.push_back(a[k]-d);  
 }  
 int main()  
 {  
   scanf("%d",&n);  
   while(scanf("%d",&a[++x])!=EOF);  
   int d=0;  
   x--;  
   solve(1,d);  
   st[0]=-maxn;  
   int top=0;  
   for(int i=0,len=v.size();i<len;i++){  
     if(v[i]>=st[top])  
       st[++top]=v[i];  
     else{  
       int k=upper_bound(st,st+top+1,v[i])-st;  
       st[k]=v[i];  
     }  
   }  
   printf("%d\n",x-top);  
   return 0;  
 }  

POJ.1145 Tree Summing

1.Problem
http://poj.org/problem?id=1145

2.Idea
Tree pre-order traversing

3.Source

 int tree_sum(int n)  
 {  
      int ans = 0, m;  
      if (scanf(" (%d", &m)) {  
           ans = tree_sum(n - m) + tree_sum(n - m);  
           if (ans < 2) ans = 0;  
      }  
      else  
           ans = !n;  
      scanf(" )");  
      return ans;  
 }  
 int main()  
 {  
      int n;  
      while (scanf("%d", &n) != EOF) {  
           if (tree_sum(n)) printf("yes\n");  
           else printf("no\n");  
      }  
      return 0;  
 }  

POJ.3321 Apple Tree

1.Problme
http://poj.org/problem?id=3321

2.Idea
A good editorail using BIT.

3.Source

 const int MAX_N = 100009;  
 int table[MAX_N+1];  
 int BIT[MAX_N+1];  
 int tos[MAX_N+1];  
 int idx[MAX_N+1];  
 bool noApple[MAX_N+1];  
 vector<int> G[MAX_N+1];  
 int N, counter;  
 inline int readint(){  
   int ret = 0, x;  
   while(x=getchar(), !('0'<=x&&x<='9'));  
   ret = (x&15);  
   while(x=getchar(), '0'<=x&&x<='9') ret = (ret<<3) + (ret<<1) + (x&15);  
   return ret;  
 }  
 inline int sum(int n){int _R=0;for(;n;n-=n&-n)_R+=BIT[n];return _R;}  
 inline int sum(int from, int to){return sum(to-1)-sum(from-1);}  
 inline void add(int n, int x){for(;n<=N;n+=n&-n)BIT[n]+=x;}  
 inline void dfs(int v){  
      int gv = G[v].size();  
      table[v] = counter++;  
      for(int i=0; i<gv; i++){  
           if(!table[G[v][i]]) dfs(G[v][i]);  
      }  
      tos[table[v]] = counter;  
 }  
 int main(){  
      N = readint();  
      for(int i=0, x, y; i<N-1; i++){  
           x = readint(), y = readint();  
           G[x].push_back(y); G[y].push_back(x);  
      }  
      counter = 1;  
      dfs(1);  
      int M = readint();  
      for(int i=0, x; i<M; i++){  
           char op;  
           scanf(" %c ",&op);  
           x = table[readint()];  
           if(op=='Q'){  
                printf("%d\n", tos[x]-x-sum(x,tos[x]));  
           }  
           else{  
                noApple[x] = !noApple[x];  
                add(x,noApple[x]?1:-1);  
           }  
      }  
      return 0;  
 }  

POJ.1330 Nearest Common Ancestors

1.Problem
http://poj.org/problem?id=1330

2.Idea
while(x!=y) {
     if(depth x < depth y) y = parent of y;
     else  x = parent of x;
}

3.Source

 const int N = 10000;  
 vector<int> a[N]; // multiple linked list, the list of children for node i is a vector  
 int f[N], r[N]; // representations of parents and hierarchy, the parent and hierarchy for node i is f[i] and r[i]  
 void DFS(int u, int dep) // Pre-order Traversal from node u  
 {  
      r[u] = dep; // node u is at hierarchy dep  
      for (vector<int>::iterator it = a[u].begin(); it != a[u].end(); ++it)  
           DFS(*it, dep + 1);// Recursion for every child of u  
 }  
 int main()  
 {  
      int casenum, num, n, i, x, y;  
      scanf("%d", &casenum); // number of test cases  
      for (num = 0; num < casenum; num++)  
      {  
           scanf("%d", &n); // number of nodes  
           for (i = 0; i < n; i++) a[i].clear(); //initialization  
           memset(f, 255, sizeof(f));  
           for (i = 0; i < n - 1; i++)  
           {  
                scanf("%d %d", &x, &y); // edge (x, y)  
                a[x - 1].push_back(y - 1); // push node (y-1) into the list of (x - 1)’s children  
                f[y - 1] = x - 1; //node(y-1)’s parent is (x-1)  
           }  
           for (i = 0; f[i] >= 0; i++); // search the root i  
           DFS(i, 0); // calculate every nodes’ hierarchy from the root  
           scanf("%d %d", &x, &y); // a pair of nodes  
           x--; y--;  
           while (x != y) // to find the Nearest Common Ancestors  
           {  
                if (r[x]>r[y]) x = f[x];  
                else y = f[y];  
           }  
           printf("%d\n", x + 1);// Output  
      }  
      return 0;  
 }