Your sentence to be filled is:
They ______ their trip at the last moment.
If you filled this sentence with "Are believed to cancelled", It would be grammatically wrong, Because we use TO With Base form of verb. For examples: To play, To do, To work, To cancel.
etc.
I think this sentence should be filled as follows:
They are believed to have cancelled their trip at the last moment.
Here, 'To have cancelled' is perfect infinitive form which works best in the your sentence.
Perfect form of infinitive is called Perfect infinitive. A Perfect infinitive is formed with To have+past participle And it refers to a time before that of the preceding verb. For an example:
I'm glad to have studied at that school.
( Here the speaker is glad that he/she has studied at that school)
Here, am is the preceding verb. I'm glad refers to the present and 'To have studied' refers before of being glad.
We do use Perfect infinitive after some verbs. For more information,
check: http://dictionary.cambridge.org/grammar/british-grammar/perfect-infinitive-with-to-to-have-worked
Reporting an earlier event in the passive voice
If the reporting happens in the present and reported event in past we use the structure : subject+passive reporting verb+To infinitive or perfect infinitive
source: http://www.grammaring.com/reporting-an-earlier-event-in-the-passive-voice
For an example:
He is believed never to have smiled at anyone.
Now, It should be clear to you that in your sentence reporting happens in the present and reported event is in past.
They are believed= reporting in the present
To have cancelled the trip at the last moment= Reported event is in the past
