I am trying to solve Problem D Div1 — 233 http://codeforces.net/contest/398/problem/D. I am getting TLE on testcase 63. Here is my submission http://codeforces.net/contest/398/submission/21266586. According to me, the time complexity of my code is O[q * (S + K)] where q is number of queries and S (S ~ 500) is constant size defined for a node to be heavy and K denotes total number of heavy nodes. A node is heavy if degree[node] > S. Please correct me if I am wrong. Can I do something better? What changes should I make in my code? Any insights would be really helpful.

Problem 1: http://www.spoj.com/problems/TOINCSEQ/ Problem 2: http://www.spoj.com/problems/TOPALIN/ Even for the partial scores, I am not able to come up with any solution. If someone can explain solution to the above problems; even if it is for the partial scores, that would be really helpful.
p.s Problems are not related. I just have doubt in both of them.