记录编号	596074	评测结果	AAAAAAAA
题目名称	大话西游	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.394 s
提交时间	2024-10-21 14:47:39	内存使用	6.86 MiB

#include<bits/stdc++.h>
using namespace std; 
const int MAXN = 200010;  
int nodeCount, queryCount, num;   
int values[MAXN], subtreeSize[MAXN], nodeId[MAXN], depthFirstNumber[MAXN], parentNode[MAXN];  
struct Edge {  
    int destination;  
    int edgeIndex;  
    int nextEdge;  
};  
Edge edges[MAXN];  
int head[MAXN], totalEdges = 1;  
struct SegmentTreeNode {  
    int left, right;  
    int minValue, maxValue;  
};  
SegmentTreeNode segmentTree[MAXN << 2];  
char command[10];  
void readInt(int &x) {  
    register char c = getchar();  
    while (!isdigit(c)) c = getchar();  
    x = 0;  
    while (isdigit(c)) {  
        x = x * 10 + c - '0';  
        c = getchar();  
    }  
}  
void addEdge(int from, int to, int edgeIndex) {  
    edges[++totalEdges].destination = to;  
    edges[totalEdges].edgeIndex = edgeIndex;  
    edges[totalEdges].nextEdge = head[from];  
    head[from] = totalEdges;  
}  
int min(int a, int b) { return a < b ? a : b; }  
int max(int a, int b) { return a < b ? b : a; }  
void dfs(int currentNode, int parentNode) {  
    subtreeSize[currentNode] = 1;  
    depthFirstNumber[currentNode] = ++num;  
    nodeId[num] = currentNode;  

    for (int edgeIndex = head[currentNode]; edgeIndex; edgeIndex = edges[edgeIndex].nextEdge) {  
        int childNode = edges[edgeIndex].destination;  
        if (childNode == parentNode) continue;  
        ::parentNode[edges[edgeIndex].edgeIndex] = childNode;  
        dfs(childNode, currentNode);  
        subtreeSize[currentNode] += subtreeSize[childNode];  
    }  
}  
void buildSegmentTree(int node, int left, int right) {  
    segmentTree[node].left = left;  
    segmentTree[node].right = right;  

    if (left == right) {  
        segmentTree[node].minValue = segmentTree[node].maxValue = values[nodeId[left]];  
        return;  
    }  

    int mid = (left + right) >> 1;  
    buildSegmentTree(node << 1, left, mid);  
    buildSegmentTree(node << 1 | 1, mid + 1, right);  
    segmentTree[node].minValue = min(segmentTree[node << 1].minValue, segmentTree[node << 1 | 1].minValue);  
    segmentTree[node].maxValue = max(segmentTree[node << 1].maxValue, segmentTree[node << 1 | 1].maxValue);  
}  
void modifySegmentTree(int node, int index, int value) {  
    if (segmentTree[node].left == segmentTree[node].right) {  
        segmentTree[node].minValue = segmentTree[node].maxValue = value;  
        return;  
    }  

    int mid = (segmentTree[node].left + segmentTree[node].right) >> 1;  
    if (index <= mid) modifySegmentTree(node << 1, index, value);  
    else modifySegmentTree(node << 1 | 1, index, value);  

    segmentTree[node].minValue = min(segmentTree[node << 1].minValue, segmentTree[node << 1 | 1].minValue);  
    segmentTree[node].maxValue = max(segmentTree[node << 1].maxValue, segmentTree[node << 1 | 1].maxValue);  
}  
int queryMin(int node, int left, int right) {  
    if (left <= segmentTree[node].left && right >= segmentTree[node].right) return segmentTree[node].minValue;  

    int minValue = 1e9;  
    int mid = (segmentTree[node].left + segmentTree[node].right) >> 1;  
    
    if (left <= mid) minValue = min(minValue, queryMin(node << 1, left, right));  
    if (right > mid) minValue = min(minValue, queryMin(node << 1 | 1, left, right));  
    
    return minValue;  
}  
int queryMax(int node, int left, int right) {  
    if (left <= segmentTree[node].left && right >= segmentTree[node].right) return segmentTree[node].maxValue;  

    int maxValue = -1;  
    int mid = (segmentTree[node].left + segmentTree[node].right) >> 1;  
    
    if (left <= mid) maxValue = max(maxValue, queryMax(node << 1, left, right));  
    if (right > mid) maxValue = max(maxValue, queryMax(node << 1 | 1, left, right));  
    
    return maxValue;  
}  

int main() {  
	freopen("westward.in","r",stdin);
	freopen("westward.out","w",stdout);
    int x, y;  
    readInt(nodeCount);  
    readInt(queryCount);  
    for (int i = 1; i <= nodeCount; ++i) {  
        readInt(values[i]);  
    }  
    for (int i = 1; i < nodeCount; ++i) {  
        readInt(x);  
        readInt(y);  
        addEdge(x, y, i);  
        addEdge(y, x, i);  
    }  
    dfs(1, 0);    
    buildSegmentTree(1, 1, nodeCount);  
    for (int i = 1; i <= queryCount; ++i) {  
        scanf("%s", command);  
        if (command[0] == 'C') {  
            readInt(x);  
            readInt(y);  
            modifySegmentTree(1, depthFirstNumber[x], y);  
        } else {  
            readInt(x);  
            int left = depthFirstNumber[parentNode[x]], right = left + subtreeSize[parentNode[x]] - 1;  
            int min1 = queryMin(1, left, right), max1 = queryMax(1, left, right);  
            int min2 = 1e9, max2 = -1;  
            if (left > 1) min2 = queryMin(1, 1, left - 1), max2 = queryMax(1, 1, left - 1);  
            if (right < nodeCount) {  
                min2 = min(min2, queryMin(1, right + 1, nodeCount));  
                max2 = max(max2, queryMax(1, right + 1, nodeCount));  
            }  
            long long answer = (long long)min1 * (long long)max1 + (long long)min2 * (long long)max2;  
            printf("%lld\n", answer);  
        }  
    }   
    return 0;  
}