ural1553 Caves and Tunnels
2024-08-24 06:03:46
Caves and Tunnels
Time limit: 3.0 second
Memory limit: 64 MB
Memory limit: 64 MB
After landing on Mars surface, scientists found a strange system of caves connected by tunnels. So they began to research it using remote controlled robots. It was found out that there exists exactly one route between every pair of caves. But then scientists faced a particular problem. Sometimes in the caves faint explosions happen. They cause emission of radioactive isotopes and increase radiation level in the cave. Unfortunately robots don't stand radiation well. But for the research purposes they must travel from one cave to another. So scientists placed sensors in every cave to monitor radiation level in the caves. And now every time they move robots they want to know the maximal radiation level the robot will have to face during its relocation. So they asked you to write a program that will solve their problem.
Input
The first line of the input contains one integer N (1 ≤ N ≤ 100000) — the number of caves. NextN − 1 lines describe tunnels. Each of these lines contains a pair of integers ai, bi(1 ≤ ai, bi ≤ N) specifying the numbers of the caves connected by corresponding tunnel. The next line has an integer Q (Q ≤ 100000) representing the number of queries. The Q queries follow on a single line each. Every query has a form of "C U V", where C is a single character and can be either 'I' or 'G' representing the type of the query (quotes for clarity only). In the case of an 'I' query radiation level in U-th cave (1 ≤ U ≤ N) is incremented by V (0 ≤ V ≤ 10000). In the case of a 'G' query your program must output the maximal level of radiation on the way between caves with numbers U and V (1 ≤ U, V ≤ N) after all increases of radiation ('I' queries) specified before current query. It is assumed that initially radiation level is 0 in all caves, and it never decreases with time (because isotopes' half-life time is much larger than the time of observations).
Output
For every 'G' query output one line containing the maximal radiation level by itself.
Sample
input | output |
---|---|
4 |
1 |
分析:树上点修改+区间极值查询,树链剖分;
代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+,mod=1e9+,inf=0x3f3f3f3f;
int n,m,k,t,tot;
int bl[maxn],pos[maxn],dep[maxn],sz[maxn],fa[maxn];
int mx[maxn<<];
vector<int>e[maxn];
void dfs(int x,int y=)
{
sz[x]=;
for(int i=;i<e[x].size();i++)
{
int z=e[x][i];
if(z==y)continue;
fa[z]=x;dep[z]=dep[x]+;
dfs(z,x);
sz[x]+=sz[z];
}
}
void dfs1(int x,int chain)
{
bl[x]=chain;
pos[x]=++tot;
int big=;
for(int i=;i<e[x].size();i++)
{
int z=e[x][i];
if(dep[z]<dep[x])continue;
if(sz[z]>sz[big])big=z;
}
if(!big)return;
dfs1(big,chain);
for(int i=;i<e[x].size();i++)
{
int z=e[x][i];
if(dep[z]<dep[x]||z==big)continue;
dfs1(z,z);
}
}
void pup(int rt){mx[rt]=max(mx[rt<<],mx[rt<<|]);}
void upd(int x,int y,int l,int r,int rt)
{
if(x==l&&x==r){mx[rt]+=y;return;}
int mid=l+r>>;
if(x<=mid)upd(x,y,l,mid,rt<<);
else upd(x,y,mid+,r,rt<<|);
pup(rt);
}
int q(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)return mx[rt];
int mid=l+r>>;
int ret=;
if(L<=mid)ret=max(ret,q(L,R,l,mid,rt<<));
if(mid+<=R)ret=max(ret,q(L,R,mid+,r,rt<<|));
return ret;
}
int main()
{
int i,j;
//freopen("in.txt","r",stdin);
scanf("%d",&n);
for(i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
dfs();
dfs1(,);
scanf("%d",&m);
while(m--)
{
char op[];
int x,y;
scanf("%s%d%d",op,&x,&y);
if(op[]=='I')upd(pos[x],y,,n,);
else
{
int ret=;
while(bl[x]!=bl[y])
{
if(dep[bl[x]]<dep[bl[y]])swap(x,y);
ret=max(ret,q(pos[bl[x]],pos[x],,n,));
x=fa[bl[x]];
}
if(pos[x]>pos[y])swap(x,y);
ret=max(ret,q(pos[x],pos[y],,n,));
printf("%d\n",ret);
}
}
return ;
}
最新文章
- ASP.NET Core真实管道详解[1]:中间件是个什么东西?
- 我也想聊聊 OAuth 2.0 —— Access Token
- linux 下如何查看和踢除正在登陆的其它用户 ==>;Linux下用于查看系统当前登录用户信息的4种方法
- visualsvn server 安装提示无法启动
- ajax 模仿百度下拉
- iOS开发——数据持久化Swift篇&;(三)SQLite3
- uva11732 strcmp() Anyone?
- 数据的软删除-管理员的CRUD
- 阿狸V任务页面爬取数据解析
- less封装样式有规律的类选择器-遁地龙卷风
- poj 1039
- ID的故事
- 了不起的Node.js--之一
- MVC中使用Web API和EntityFramework
- Android自定义控件-折线图
- VMware下安装的Mac OS X如何修改显示分辨率 (转)
- jquery中的$().each和$.each的区别
- 用google mock模拟C++对象
- 使用Berkeley Parser进行句法分析
- compositionstart 、 compositionend 、 input都存在时的解决办法