今思えば簡単だった…各ノードにたいして持っておくのはpriority_queue。中身の合計も別に持っておく。 DFS調に下から各ノードに対して満足度を求めていく。大事なこととして、 「最初にpriority_queueに子ノードたちのぶんを合体させて持っておく。(いぱテク…

こんなのsegment treeでO(n log n)で余裕だな！とやってたらずっとTLEしていて頭が悪い… [0,a]と[b,n]のクエリしか使わないんだから線形でしょうに・・・ #include<stdio.h> #include<algorithm> using namespace std; int b[1100000]; char str[5000000]; int sz; int c[1048576</algorithm></stdio.h>…