The following problem popped into my mind all of a sudden and I have no idea how to solve it.

You are given a weighted rooted tree with $$$n$$$ nodes. You need to find the number of unordered pairs of nodes $$$(u,v)$$$ such that

$$$Constraints: 1<=n<= 10^5, -10^6<=edge\,weights<=10^6$$$

It will be really helpful if you can provide me with a solution.

Well, one can count the number of primes less than or equal to n in (correct me if I am wrong) using Prime-counting function. You can solve this beautiful problem using the idea.

But recently I have come across following two (this and this) SPOJ problems with tag and have no idea how to solve them.

So If anyone can give me any idea about how to solve them, anyone will be appreciated respectfully. Thanks.

I am stuck on this following problem:

Statement:

Given a string of size n, for each i from 1 to n you need to find if the string can be split into i non-empty non-intersecting palindromes. Output YES/NO.

Constraints:

1<=n<=100000

Example:

Input:

aabaa

Output:

YES

NO

YES

YES

YES

Explanation

aabaa(1 palindrome), aa|b|aa(3 palindromes), a|b|a|aa(4 palindromes), a|b|a|a|a(5 palindromes)

Notice that you can not split the string into 2 palindromes.

Trivia:

Thanks for reading the problem. It will be really helpful if you can provide me with a solution.

I am stuck on this following problem:

Statement:

Given an undirected connected simple graph of n nodes and m edges, for each node i from 1 to n you need to find if this node was not present in this graph how many connected components the graph would have.

Constraints:

1<=n,m<=100000

Example:

Input:

4 4 //4 nodes and 4 edges

1 2

2 3

2 4

3 4

Output:

1 2 1 1

Note:

A node is not present means erasing the node and its edges

Trivia:

Thanks for reading the problem. It will be really helpful if you can give me a solution.

I am stuck on this following problem:

Statement:

Given a string of size n and q queries of type (l,r) you need to find how many palindromes are there in the substring of range [l...r].

Constraints:

1<=n,q<=100000

1<=l<=r<=n

Thanks for reading the problem. It will be really helpful if you can give me a solution.

I need to solve this following problem as a subproblem of another problem:

Statement:

You are given n sets S[1], S[2], S[3], ..., S[n] each having some distinct elements (Note that 2 different sets have common elements but each set have distinct elements).

Given q queries of type (i,j) you need to find if there is any common element in set S[i] and S[j]. Output YES/NO.

Constraints:

1<= n,size of S[i],elements of S[i],q <=100000

1<= sum of sizes of all sets <=100000

Thanks for reading the problem. It will be great if you can give me a solution.

I need to solve the following task as a subtask of another problem. So I need your HELP.

I need a Data Structure that can do the following operations:

1. Add a pair of integers (x,y) in the Data Structure.

2. For a given pair (a,b) it will give me the count of the number of pairs (x,y) such that x<=a and y<=b.

Note: Maximum Time Complexity for both of the operations can be at most O(log n).

Trivia: (not for this problem) I am interested if there is a solution with erase operation.