1612. 大话西游
http://www.cogs.pro/cogs/problem/problem.php?pid=1612
★★ 输入文件：westward.in 输出文件：westward.out 简单对比
时间限制：1 s 内存限制：256 MB
【题目描述】
“大话西游”是一个在中国非常流行的在线游戏，由NIE公司开发和维护。这个游戏来源于著名的小说《西游记》和周星弛的电影，游戏的背景故事充满奇幻色彩，引人入胜。
游戏里面有很多片区域，不同的区域由不同的统治者管辖，其中有一个地方名叫“树国”，由一个妖怪控制着。这里有N个城堡，每个城堡都有其重要程度值（一个正整数，不超过10^8），这些城堡被N-1条双向道路所连接，任意两个城堡均可互达，城堡的重要程度值是可变的。现在，妖怪想知道如果破坏其中的一条道路会发生什么。本题中，你总共需要处理Q条指令，每一个都具有下面所述的格式：
(1)CHANGE
i w
本指令的含义为：将第i个城堡的重要程度值变为w（1<=w<=10^8）
(2)QUERY
j
本指令的含义为：输出min1*max1+min2*max2的值，详细如下：
第j条道路可以把“树国”分成两个连通块，分别称为part1和part2，其中
min1为part1中的最小重要程度值；
max1为part1中的最大重要程度值；
min2为part2中的最小重要程度值；
max2为part2中的最大重要程度值。
【输入格式】
第一行有两个整数N(2<=N<=100000)和Q(1<=Q<=100000),分别表示城堡的个数及指令的数目。
接下来的一行有N个整数(正整数，不超过10^8)，表示起初每一个城堡的重要程度值(城堡的编号为1～N)。
接下来有N-1行，每行有两个整数u,v，表示在城堡u和城堡v之间有一条无向边相连，（边的编号依次为1~N-1）。
接下来有Q行，每行有一个指令，格式如下所述。
【输出格式】
对于每个"QUERY"指令，在单独一行输出结果。
【样例输入】
5 3 1 2 3 4 5 1 2 2 3 3 4 4 5 QUERY 1 CHANGE 1 10 QUERY 1
【样例输出】
11 110
维护每个点的dfs序，以此为建线段树的根据。
由于一棵子树上所有点的dfs序都是连续的，所以在查询时只需区间查询即可，这题不涉及边权，所以修改也是普通的单点修改。
只用到了树剖的第一个dfs，为的是求dfs序和子数大小
#include<cstdio> #include<iostream> using namespace std; #define maxn 100010 int num,n,q,g,Ev[maxn],fa[maxn],dfn[maxn],id[maxn],head[maxn],point[maxn],sz[maxn]; struct node{int to,pre,d;}e[maxn*4]; struct Node{int l,r,mn,mx;}tr[maxn*4]; void Insert(int from,int to,int d){e[++num].to=to,e[num].d=d;e[num].pre=head[from];head[from]=num;} void dfs(int father,int now){ sz[now]=1; dfn[now]=++g; fa[now]=father; id[g]=now; for(int i=head[now];i;i=e[i].pre){ int to=e[i].to; if(to==father)continue; point[e[i].d]=to; dfs(now,to); sz[now]+=sz[to]; } } void up(int k){ tr[k].mn=min(tr[k<<1].mn,tr[(k<<1)|1].mn); tr[k].mx=max(tr[k<<1].mx,tr[(k<<1)|1].mx); } void build(int l,int r,int k){ tr[k].l=l;tr[k].r=r; if(tr[k].l==tr[k].r){tr[k].mn=tr[k].mx=Ev[id[l]];return;} int mid=(l+r)>>1; build(l,mid,k<<1);build(mid+1,r,(k<<1)|1); up(k); } int findmax(int l,int r,int k){ if(tr[k].l==l&&tr[k].r==r)return tr[k].mx; int mid=(tr[k].l+tr[k].r)>>1; if(r<=mid)return findmax(l,r,k<<1); else if(l>mid)return findmax(l,r,(k<<1)|1); else return max(findmax(l,mid,k<<1),findmax(mid+1,r,(k<<1)|1)); } int findmin(int l,int r,int k){ if(tr[k].l==l&&tr[k].r==r)return tr[k].mn; int mid=(tr[k].l+tr[k].r)>>1; if(r<=mid)return findmin(l,r,k<<1); else if(l>mid)return findmin(l,r,(k<<1)|1); else return min(findmin(l,mid,k<<1),findmin(mid+1,r,(k<<1)|1)); } void update(int pos,int v,int k){ if(tr[k].l==tr[k].r){tr[k].mn=tr[k].mx=v;return;} int mid=(tr[k].l+tr[k].r)>>1; if(pos<=mid)update(pos,v,k<<1); if(pos>mid)update(pos,v,(k<<1)|1); up(k); } int main(){ freopen("westward.in","r",stdin); freopen("westward.out","w",stdout); //freopen("Cola.txt","r",stdin); scanf("%d%d",&n,&q); for(int i=1;i<=n;i++)scanf("%d",&Ev[i]); int x,y; for(int i=1;i<n;i++){ scanf("%d%d",&x,&y); Insert(x,y,i);Insert(y,x,i); } dfs(0,1); build(1,n,1); char ch[10]; for(int i=1;i<=q;i++){ scanf("%s",&ch); int a,b; if(ch[0]=='C'){ scanf("%d%d",&a,&b); update(dfn[a],b,1); } if(ch[0]=='Q'){ scanf("%d",&a); int s=dfn[point[a]],t=s+sz[point[a]]-1; int max1,max2;int min1,min2;min1=min2=0x7fffffff; max1=findmax(s,t,1);min1=findmin(s,t,1); if(s!=1)max2=findmax(1,s-1,1),min2=findmin(1,s-1,1); if(t!=n) max2=max(max2,findmax(t+1,n,1)),min2=min(min2,findmin(t+1,n,1)); //int ans=min1*max1+min2*max2; printf("%lld ",(long long)min1*(long long)max1+(long long)min2*(long long)max2); } } return 0; }