为一下LZ是什么专业的?为什么学C++?难道是搞信息的?表示对现在大学教的内容不解,求LZ介绍
顺便贴个小程序,一道题目,前一段写的(ZJOI《树的统计》 - 树链剖分)
/*
Title: count
Data: 2011-1-30
*/
#include <iostream>
#include <memory.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define InputFileName "XXXXXXXX"
#define OutputFileName "count.out"
using namespace std;
const int MaxN = 31000, oo = 0x7FFFFFFF;
bool View[MaxN];
int n, m, u[MaxN*2], v[MaxN*2], Next[MaxN*2], Head[MaxN], w[MaxN], Size[MaxN], ENum, Heavy[MaxN], Depth[MaxN], d[MaxN*2][20], Pos[MaxN], Total, Line[MaxN], Father[MaxN];
int Left[MaxN*4], Right[MaxN*4], Sum[MaxN*4], MaxNum[MaxN*4], STNum[MaxN], STSize[MaxN], STTotal, Root[MaxN], STPos[MaxN], S[MaxN], T[MaxN];
inline void AddEdge(const int x, const int y)
{
Next[++ENum] = Head[x];
Head[x] = ENum;
u[ENum] = x;
v[ENum] = y;
}
void Init()
{
scanf("%d", &n);
for (int i = 1, x, y; i < n; ++i)
{
scanf("%d%d", &x, &y);
AddEdge(x, y);
AddEdge(y, x);
}
for (int i = 1; i <= n; ++i)
scanf("%d", w+i);
scanf("%d", &m);
}
void DFS(const int t)
{
View[t] = Size[t] = 1;
d[Pos[t] = ++Total][0] = t;
for (int i = Head[t]; i; i = Next[i])
if (! View[v[i]])
{
Depth[v[i]] = Depth[Father[v[i]] = t]+1;
DFS(v[i]);
d[++Total][0] = t;
Size[t] += Size[v[i]];
if (! Heavy[t] || Size[Heavy[t]] < Size[v[i]])
Heavy[t] = v[i];
}
}
inline int Max(const int x, const int y)
{
return x > y ? x : y;
}
inline int RMQMin(const int x, const int y)
{
return Depth[x] < Depth[y] ? x : y;
}
void RMQInitialize()
{
for (int i, j = 1, k = (int)(log2(Total)+1E-8), l; j <= k; ++j)
for (i = 1, l = 1 << j; i+l-1 <= Total; ++i)
d[i][j] = RMQMin(d[i][j-1], d[i+(l >> 1)][j-1]);
}
inline int RMQ(int x, int y)
{
if (Pos[x] > Pos[y])
{
int z = x;
x = y;
y = z;
}
const int k = (int)(log2(Pos[y]-Pos[x]+1)+1E-8);
return RMQMin(d[Pos[x]][k], d[Pos[y]-(1 << k)+1][k]);
}
void NewTree(const int t, const int l, const int r)
{
if (l == r)
{
Sum[t] = MaxNum[t] = w[Line[l]];
return;
}
const int mid = l+r >> 1;
NewTree(Left[t] = ++STTotal, l, mid);
NewTree(Right[t] = ++STTotal, mid+1, r);
Sum[t] = Sum[Left[t]]+Sum[Right[t]];
MaxNum[t] = Max(MaxNum[Left[t]], MaxNum[Right[t]]);
}
void Build()
{
memset(View, 0, sizeof(View));
Total = 0;
for (int k = 1, i, j; k < 2*n; ++k)
if (! View[i = d[k][0]])
{
for (View[Line[STPos[i] = STSize[++Total] = 1] = j = i] = 1; Heavy[j]; View[Line[STPos[Heavy[j]] = ++STSize[Total]] = j = Heavy[j]] = 1);
S[Total] = i;
T[Total] = j;
for (STNum[j = i] = Total; Heavy[j]; STNum[j = Heavy[j]] = Total);
NewTree(Root[Total] = ++STTotal, 1, STSize[Total]);
}
}
void Modify(const int t, const int l, const int r, const int p, const int k)
{
if (l == r)
{
Sum[t] = MaxNum[t] = k;
return;
}
const int mid = l+r >> 1;
if (p <= mid)
Modify(Left[t], l, mid, p, k);
else
Modify(Right[t], mid+1, r, p, k);
Sum[t] = Sum[Left[t]]+Sum[Right[t]];
MaxNum[t] = Max(MaxNum[Left[t]], MaxNum[Right[t]]);
}
int STSum(const int t, const int l, const int r, const int x, const int y)
{
if (x <= l && y >= r)
return Sum[t];
int mid = l+r >> 1, Res = 0;
if (x <= mid)
Res = STSum(Left[t], l, mid, x, y);
if (y > mid)
Res += STSum(Right[t], mid+1, r, x, y);
return Res;
}
int STMax(const int t, const int l, const int r, const int x, const int y)
{
if (x <= l && y >= r)
return MaxNum[t];
int mid = l+r >> 1, Res = -oo;
if (x <= mid)
Res = STMax(Left[t], l, mid, x, y);
if (y > mid)
Res = Max(Res, STMax(Right[t], mid+1, r, x, y));
return Res;
}
inline int GetSum(const int x, int y)
{
int Res = 0;
for (; Depth[x] < Depth[S[STNum[y]]]; y = Father[S[STNum[y]]])
Res += STSum(Root[STNum[y]], 1, STSize[STNum[y]], 1, STPos[y]);
Res += STSum(Root[STNum[y]], 1, STSize[STNum[y]], STPos[x], STPos[y]);
return Res;
}
inline int GetMax(const int x, int y)
{
int Res = -oo;
for (; Depth[x] < Depth[S[STNum[y]]]; y = Father[S[STNum[y]]])
Res = Max(Res, STMax(Root[STNum[y]], 1, STSize[STNum[y]], 1, STPos[y]));
Res = Max(Res, STMax(Root[STNum[y]], 1, STSize[STNum[y]], STPos[x], STPos[y]));
return Res;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen(InputFileName, "r", stdin);
freopen(OutputFileName, "w", stdout);
#endif
Init();
memset(View, 0, sizeof(View));
Depth[1] = 1;
DFS(1);
RMQInitialize();
Build();
char cmd[10];
int x, y, LCA, Ans, sx, sy;
for (; m; --m)
{
scanf("%s%d%d", cmd, &x, &y);
if (cmd[0] == 'C')
Modify(Root[STNum[x]], 1, STSize[STNum[x]], STPos[x], w[x] = y);
else
{
LCA = RMQ(x, y);
if (cmd[1] == 'M')
Ans = Max(GetMax(LCA, x), GetMax(LCA, y));
else
Ans = GetSum(LCA, x)+GetSum(LCA, y)-w[LCA];
printf("%d\\n", Ans);
}
}
return 0;
}
200字以内,仅用于支线交流,主线讨论请采用回复功能。