# Участник:Taranov srg/Grass planting

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

C++ 14 clang 8.0

```#include <cstdio>
#include <vector>
#include <fstream>
#include <iostream>

#define LSOne(S) (S & (-S))

using namespace std;

typedef pair <int,int> ii;

const int NMAX = 100010;
const ii NNULL = make_pair(NMAX,NMAX);

int dfsNum, chainNum, chainPtr, sub_root, par[NMAX], level[NMAX], vec[NMAX], chainHeads[NMAX], chainId[NMAX], chainPos[NMAX], edges[NMAX], tree_size[NMAX];
vector<int> graph[NMAX];
ii tree[8*NMAX],coords[2*NMAX];

void dfs(int x,int p){
vec[x] = ++dfsNum;
coords[dfsNum] = make_pair(level[x],x);
tree_size[x]++;
for (int v : graph[x]){
if (v == p) continue;
par[v] = x;
level[v] = level[x] + 1;
dfs(v,x);
tree_size[x] += tree_size[v];
coords[++dfsNum] = make_pair(level[x],x);
}
}

void HLD(int x,int p){

chainId[x] = chainNum;
chainPos[x] = ++chainPtr;
if (tree_size[x] == 1) return;

int mx = 0, argmx = -1;
for (int v : graph[x]){
if (v == p) continue;
if (tree_size[v] > mx){
mx = tree_size[v];
argmx = v;
}
}

HLD(argmx,x);
for (int v : graph[x]){
if (v == p || v == argmx) continue;
chainNum++;
HLD(v,x);
}
}

void update_ed(int pos,int val){
while (pos < NMAX){
edges[pos] += val;
pos += LSOne(pos);
}
}

int query_ed(int pos){
int ans = 0;
while (pos > 0){
ans += edges[pos];
pos -= LSOne(pos);
}
return ans;
}

void build_seg(int pos,int left,int right){
if (left == right){
tree[pos] = coords[left];
return;
}
int mid = (left+right)/2;
build_seg(2*pos,left,mid);
build_seg(2*pos+1,mid+1,right);
tree[pos] = min(tree[2*pos],tree[2*pos+1]);
}

ii query_seg(int pos,int left,int right,int i,int j){
if (left > right || left > j || right < i) return NNULL;
if (left >= i && right <= j){
return tree[pos];
}
int mid = (left+right)/2;
return min(query_seg(2*pos,left,mid,i,j),query_seg(2*pos+1,mid+1,right,i,j));
}

int LCA(int v1, int v2){
return query_seg(1,1,dfsNum,min(vec[v1],vec[v2]),max(vec[v1],vec[v2])).second;
}

void query_up(int v1,int v2){
int v1_ch,v2_ch;
v2_ch = chainId[v2];
while (true){
v1_ch = chainId[v1];
if (v1 == v2) break;
if (v1_ch == v2_ch){
update_ed(chainPos[v2]+1,1);
update_ed(chainPos[v1]+1,-1);
break;
}
update_ed(chainPos[v1]+1,-1);
v1 = par[v1];
}
}

void doQuery(int u,int v){
sub_root = LCA(u,v);
query_up(u,sub_root);
query_up(v,sub_root);
}

int main(){
int N, M, i, v1, v2;
ifstream input_file;
input_file.open("input.txt");
scanf("%d %d",&N,&M);
// input_file >> N >> M;
for (i=1; i<N; i++) {

scanf("%d %d",&v1,&v2);
// input_file >> v1 >> v2;
graph[v1].push_back(v2);
graph[v2].push_back(v1);
}

par[1] = 1;
dfs(1,-1);
build_seg(1,1,dfsNum);
chainNum++;
HLD(1,-1);

for (i=0; i<M; ++i){
char op;
scanf(" %c",&op);
// input_file >> op;
// input_file >> v1 >> v2;
scanf("%d %d",&v1,&v2);
if (op == 'P') doQuery(v1,v2);
else {
if(level[v1] < level[v2]) swap(v1,v2);
printf("%d\n",query_ed(chainPos[v1]));
}
}
return 0;
}```