Option A is correct
MaxST can be solved in polynomial time.
Just negate the weights of the edges of the graph and apply Kruskal for finding minimum spanning tree.
LongP is a Np complete problem so it takes exponential time dont have any polynomial time except for DAG (directed acyclic graph)
The algo for finding the LongP in DAG is given below.
Let us assume v0,v1,.....vn be n vertices of the dag
Suppose v0 be the source from where we have to calculate the LongP for the dag
Here we take a queue Q and an array C[n]
Initialise C[i] = - infinity for i>0 and C[0] =0
STEP 1 Enqueue v0
STEP 2 Enqueue all vertices present in the adjacency list of head(Q) which are not queued already
If any vertex vj is adjacent to head(Q) then C[j] = max ( C[j] , C[head(Q)] + weight of the edge (head(Q),vj ) )
STEP 3 Dequeue and then go to STEP 2 repeat STEP 2 and STEP 3 until there is no vertex left be queued.
STEP 4 Return max of the array C.
The above algo will take O(V + E) time.