題目描述

給出一棵有?n?個節點的樹，有?m?個如下所示的操作：

• 將兩個節點之間的?路徑上的邊?的權值均加一。

• 查詢兩個節點之間的?那一條邊?的權值，保證兩個節點直接相連。

初始邊權均為 0。

輸入格式

第一行兩個整數?n,m，含義如上。

接下來?n?1?行，每行兩個整數?u,v，表示?u,v?之間有一條邊。

接下來?m?行，每行格式為?op u v，op=P?代表第一個操作，op=Q?代表第二個操作。

輸出格式

若干行。對于每個查詢操作，輸出一行整數，代表查詢的答案。

顯示翻譯

題意翻譯

輸入輸出樣例

輸入 #1復制

4 6 
1 4 
2 4 
3 4 
P 2 3 
P 1 3 
Q 3 4 
P 1 4 
Q 2 4 
Q 1 4 

輸出 #1復制

2 
1 
2 

說明/提示

對于?100%?的數據，2≤n≤105，1≤m≤105。

代碼實現：

#include<bits/stdc++.h>
using namespace std;

// 節點數量和操作數量
int nodeCount, operationCount;

// 存儲每個節點的父節點
int parentOfNode[100001];?
// 存儲每個節點在樹中的深度
int depthOfNode[100001];?
// 存儲每個節點的重兒子節點
int heavySonOfNode[100001];?
// 存儲以每個節點為根的子樹的節點數量
int subtreeNodeCount[100001];?
// 存儲每個節點所在重鏈的頂端節點
int topNodeOfChain[100001];?
// 存儲每個節點在線段樹中的位置編號
int segmentTreePosition[100001];?

// 使用 vector 存儲圖的鄰接表
vector<int> graph[100001];?

// 第一次深度優先搜索，用于計算節點的深度、重兒子、子樹節點數量等信息
void firstDFS(int currentNode, int parentNode, int currentDepth) {
? ? parentOfNode[currentNode] = parentNode;
? ? depthOfNode[currentNode] = currentDepth;
? ? subtreeNodeCount[currentNode] = 1;
? ? int maxSubtreeSize = 0;

? ? for (int i = 0; i < graph[currentNode].size(); i++) {
? ? ? ? int adjacentNode = graph[currentNode][i];
? ? ? ? if (adjacentNode!= parentNode) {
? ? ? ? ? ? firstDFS(adjacentNode, currentNode, currentDepth + 1);
? ? ? ? ? ? subtreeNodeCount[currentNode] += subtreeNodeCount[adjacentNode];
? ? ? ? ? ? if (maxSubtreeSize < subtreeNodeCount[adjacentNode]) {
? ? ? ? ? ? ? ? heavySonOfNode[currentNode] = adjacentNode;
? ? ? ? ? ? ? ? maxSubtreeSize = subtreeNodeCount[adjacentNode];
? ? ? ? ? ? }
? ? ? ? }
? ? }
}

// 第二次深度優先搜索，用于構建重鏈剖分
void secondDFS(int currentNode, int chainTopNode) {
? ? topNodeOfChain[currentNode] = chainTopNode;
? ? segmentTreePosition[currentNode] = ++segmentTreePosition[0];
? ? if (!heavySonOfNode[currentNode]) return;
? ? secondDFS(heavySonOfNode[currentNode], chainTopNode);

? ? for (int i = 0; i < graph[currentNode].size(); i++) {
? ? ? ? int adjacentNode = graph[currentNode][i];
? ? ? ? if (parentOfNode[currentNode] == adjacentNode || heavySonOfNode[currentNode] == adjacentNode) continue;
? ? ? ? secondDFS(adjacentNode, adjacentNode);
? ? }
}

// 線段樹節點結構體
struct SegmentTreeNode {
? ? int leftBound;
? ? int rightBound;
? ? int sumValue;
? ? int lazyAddValue;
};

SegmentTreeNode segmentTree[400001];

// 構建線段樹
void buildSegmentTree(int treeNodeIndex, int left, int right) {
? ? segmentTree[treeNodeIndex].leftBound = left;
? ? segmentTree[treeNodeIndex].rightBound = right;
? ? if (left == right) return;
? ? buildSegmentTree(treeNodeIndex * 2, left, (left + right) / 2);
? ? buildSegmentTree(treeNodeIndex * 2 + 1, (left + right) / 2 + 1, right);
}

// 下傳線段樹的懶標記
void pushDownLazyTag(int treeNodeIndex) {
? ? segmentTree[treeNodeIndex * 2].lazyAddValue += segmentTree[treeNodeIndex].lazyAddValue;
? ? segmentTree[treeNodeIndex * 2 + 1].lazyAddValue += segmentTree[treeNodeIndex].lazyAddValue;
? ? segmentTree[treeNodeIndex * 2].sumValue += (segmentTree[treeNodeIndex * 2].rightBound - segmentTree[treeNodeIndex * 2].leftBound + 1) * segmentTree[treeNodeIndex].lazyAddValue;
? ? segmentTree[treeNodeIndex * 2 + 1].sumValue += (segmentTree[treeNodeIndex * 2 + 1].rightBound - segmentTree[treeNodeIndex * 2 + 1].leftBound + 1) * segmentTree[treeNodeIndex].lazyAddValue;
? ? segmentTree[treeNodeIndex].lazyAddValue = 0;
}

// 在線段樹上進行區間修改操作
void updateSegmentTree(int treeNodeIndex, int left, int right) {
? ? if (segmentTree[treeNodeIndex].rightBound < left || segmentTree[treeNodeIndex].leftBound > right) return;
? ? if (segmentTree[treeNodeIndex].leftBound >= left && segmentTree[treeNodeIndex].rightBound <= right) {
? ? ? ? segmentTree[treeNodeIndex].sumValue += segmentTree[treeNodeIndex].rightBound - segmentTree[treeNodeIndex].leftBound + 1;
? ? ? ? segmentTree[treeNodeIndex].lazyAddValue++;
? ? ? ? return;
? ? }
? ? pushDownLazyTag(treeNodeIndex);
? ? updateSegmentTree(treeNodeIndex * 2, left, right);
? ? updateSegmentTree(treeNodeIndex * 2 + 1, left, right);
? ? segmentTree[treeNodeIndex].sumValue = segmentTree[treeNodeIndex * 2].sumValue + segmentTree[treeNodeIndex * 2 + 1].sumValue;
}

// 在線段樹上查詢單點的值
int querySegmentTree(int treeNodeIndex, int targetPosition) {
? ? if (segmentTree[treeNodeIndex].rightBound < targetPosition || segmentTree[treeNodeIndex].leftBound > targetPosition) return 0;
? ? if (segmentTree[treeNodeIndex].leftBound == segmentTree[treeNodeIndex].rightBound) return segmentTree[treeNodeIndex].sumValue;
? ? pushDownLazyTag(treeNodeIndex);
? ? return querySegmentTree(treeNodeIndex * 2, targetPosition) + querySegmentTree(treeNodeIndex * 2 + 1, targetPosition);
}

int main() {
? ? int node1, node2;
? ? char operationType;
? ? cin >> nodeCount >> operationCount;
? ? for (int i = 1; i < nodeCount; i++) {
? ? ? ? cin >> node1 >> node2;
? ? ? ? graph[node1].push_back(node2);
? ? ? ? graph[node2].push_back(node1); // 存儲無向邊
? ? }

? ? firstDFS(1, 0, 1);
? ? secondDFS(1, 1);
? ? buildSegmentTree(1, 1, nodeCount);

? ? while (operationCount--) {
? ? ? ? cin >> operationType >> node1 >> node2;
? ? ? ? if (operationType == 'P') {
? ? ? ? ? ? while (topNodeOfChain[node1]!= topNodeOfChain[node2]) {
? ? ? ? ? ? ? ? if (depthOfNode[topNodeOfChain[node1]] < depthOfNode[topNodeOfChain[node2]]) swap(node1, node2);
? ? ? ? ? ? ? ? updateSegmentTree(1, segmentTreePosition[topNodeOfChain[node1]], segmentTreePosition[node1]);
? ? ? ? ? ? ? ? node1 = parentOfNode[topNodeOfChain[node1]];
? ? ? ? ? ? }
? ? ? ? ? ? if (depthOfNode[node1] > depthOfNode[node2]) swap(node1, node2);
? ? ? ? ? ? updateSegmentTree(1, segmentTreePosition[node1] + 1, segmentTreePosition[node2]); // 避開最近公共祖先
? ? ? ? } else {
? ? ? ? ? ? if (parentOfNode[node1] == node2) cout << querySegmentTree(1, segmentTreePosition[node1]) << endl;
? ? ? ? ? ? else cout << querySegmentTree(1, segmentTreePosition[node2]) << endl; // 判斷該邊的邊權是哪個點的點權
? ? ? ? }
? ? }
? ? return 0;
}