#include #include #define SALESMAN_MAX 500001 #define EULER_MAX (SALESMAN_MAX*2) #define SEG_MAX EULER_MAX*4 #define ll long long typedef struct Node{ int nodeNumber; struct Node* next; }Node; Node* head[SALESMAN_MAX]; Node Edges[SALESMAN_MAX*2]; int salary[SALESMAN_MAX]; int euler[EULER_MAX]; int firstVisit[SALESMAN_MAX]; int finalVisit[SALESMAN_MAX]; int eulerDepth[EULER_MAX]; int eulerN; ll seg[SEG_MAX]; ll prefixSum[SEG_MAX]; Node* makeNode(int nodeNumber){ Node* newnode = (Node*)malloc(sizeof(Node)); newnode->nodeNumber = nodeNumber; return newnode; } void makeTree(int parent, Node* newnode){ newnode->next = head[parent]; head[parent] = newnode; } void dfsTree(int headIndex, int depth, int parent){ if(firstVisit[headIndex] == -1) firstVisit[headIndex] = eulerN; euler[eulerN] = headIndex; eulerDepth[eulerN] = depth; finalVisit[headIndex] = eulerN; eulerN++; for(Node* p = head[headIndex]; p; p = p->next){ if(p->nodeNumber != parent){ dfsTree(p->nodeNumber, depth + 1, headIndex); euler[eulerN] = headIndex; eulerDepth[eulerN] = depth; finalVisit[headIndex] = eulerN; eulerN++; } } } void updateLazy(int front, int end, int index){ if(prefixSum[index] == 0) return; seg[index] += (end - front + 1)*prefixSum[index]; if(front != end){ prefixSum[index*2] += prefixSum[index]; prefixSum[index*2 + 1] += prefixSum[index]; } prefixSum[index] = 0; } void updateRange(int front, int end, int index, int left, int right, int salary){ updateLazy(front, end, index); if(right < front || end < left) return; if(left <= front && end <= right){ seg[index] += (end - front + 1)*salary; if(front != end){ prefixSum[index*2] += salary; prefixSum[index*2 + 1] += salary; } return; } int mid = (front + end)/2; updateRange(front, mid, index*2, left, right, salary); updateRange(mid + 1, end, index*2 + 1, left, right, salary); seg[index] = seg[index*2] + seg[index*2 + 1]; } ll findsalary(int front, int end, int index, int dest){ updateLazy(front, end, index); if(dest < front || end < dest) return 0; if(front == end) return seg[index]; int mid = (front + end)/2; return findsalary(front, mid, index*2, dest) + findsalary(mid + 1, end, index*2 + 1, dest); } void makeSeg(int employeeN){ for(int i=1; i<=employeeN; i++){ updateRange(0, eulerN - 1, 1, firstVisit[i], firstVisit[i], salary[i]); } } int main(void){ int employeeN; int queryN; int parent = 0; int nodeNumber; int cost; char kind; scanf("%d%d%d", &employeeN, &queryN, &salary[1]); makeTree(0, makeNode(1)); for(int i=2; i<=employeeN; i++){ scanf("%d%d", &salary[i], &parent); makeTree(parent, makeNode(i)); } for(int i=0; i<=employeeN; i++) firstVisit[i] = -1; dfsTree(1, 0, 0); makeSeg(employeeN); for(int i=0; i

제출 #159134

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: