【LSGDOJ1834 Tree】树链剖分

题目描述

给定一个N个结点的无向树，树中的结点按照1...N编号，树中的边按照1...N − 1编号，每条边都赋予一个权值。你需要编写程序支持以下三种操作：

1. CHANGE i v：将i号边的权值改为v。

2. NEGATE a b：将结点a到结点b路径上每条边权值取相反数。例如NEGATE(-3)=3,

NEGATE(3)=-3。

3. QUERY a b：返回结点a到结点b路径上权值最大边的权值。

输入

第一行为N(N ≤ 105)，代表树中结点的个数。

接下来N − 1行，每行三个整数x y w表示有一条连接结点x和y的边，权值为w。

接下来若干行代表了三种操作。操作的格式见问题描述。遇到一行“DONE”时结束。

不会超过105个操作（不包含DONE）。

输入数据中有30%的数据，满足N ≤ 100。

输出

对于每个QUERY操作，输出一行，代表最大的权值。

样例输入

3 1 2 1 2 3 2 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE

样例输出

1 3

题解：

树链剖分水题，但小测的时候打错了，发个博客以泄愤。

关键：线段树中不仅维护最大值又要维护最小值，然后取反就相当于swap(最小值，最大值).

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #define ls (node<<1)
  7 #define rs (node<<1|1)
  8 using namespace std;
  9 const int N=100005,INF=1999999999;
 10 int n;
 11 int gi()
 12 {
 13     int str=0,f=1;char ch=getchar();
 14     while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
 15     while(ch>='0' && ch<='9')str=str*10+ch-'0',ch=getchar();
 16     return str*f;
 17 }
 18 int num=0,head[N],haha[N];char s[15];
 19 struct TT{
 20     int minn,maxn;
 21 }Tree[N*4];
 22 int mark[N*4];
 23 struct Lin{
 24     int next,to,dis;
 25 }a[N*2];
 26 struct Edge{
 27     int x,y,z;
 28 }e[N];
 29 void updata(int node){
 30     Tree[node].maxn=Tree[ls].maxn>Tree[rs].maxn?Tree[ls].maxn:Tree[rs].maxn;
 31     Tree[node].minn=Tree[ls].minn<Tree[rs].minn?Tree[ls].minn:Tree[rs].minn;
 32 }
 33 void init(int x,int y,int z)
 34 {
 35     a[++num].next=head[x];
 36     a[num].to=y;
 37     a[num].dis=z;
 38     head[x]=num;
 39     a[++num].next=head[y];
 40     a[num].to=x;
 41     a[num].dis=z;
 42     head[y]=num;
 43 }
 44 int top[N],dep[N],id[N],son[N],fa[N],size[N],ids=0;
 45 void dfs1(int x)
 46 {
 47     int u;
 48     size[x]=1;
 49     for(int i=head[x];i;i=a[i].next)
 50     {
 51         u=a[i].to;
 52         if(dep[u])continue;
 53         dep[u]=dep[x]+1;fa[u]=x;
 54         dfs1(u);
 55         size[x]+=size[u];if(size[u]>size[son[x]])son[x]=u;
 56     }
 57 }
 58 void dfs2(int x,int tp)
 59 {
 60     id[x]=++ids;top[x]=tp;
 61     if(son[x])dfs2(son[x],tp);
 62     int u;
 63     for(int i=head[x];i;i=a[i].next){
 64         u=a[i].to;
 65         if(u==son[x] || u==fa[x])continue;
 66         dfs2(u,u);
 67     }
 68 }
 69 void build(int l,int r,int node)
 70 {
 71     mark[node]=0;
 72     if(l==r){Tree[node].maxn=Tree[node].minn=haha[l];return ;}
 73     int mid=(l+r)>>1;
 74     build(l,mid,ls);
 75     build(mid+1,r,rs);
 76     updata(node);
 77 }
 78 void pushdown(int node)
 79 {
 80     if(!mark[node])return ;
 81     mark[ls]^=1;mark[rs]^=1;
 82     swap(Tree[rs].maxn,Tree[rs].minn);Tree[ls].maxn*=-1;Tree[ls].minn*=-1;
 83     swap(Tree[ls].maxn,Tree[ls].minn);Tree[rs].maxn*=-1;Tree[rs].minn*=-1;
 84     mark[node]=0;
 85 }
 86 void cg(int l,int r,int node,int sa,int se,int toit)
 87 {
 88     if(l>se || r<sa)return ;
 89     if(sa<=l && r<=se){
 90         if(toit==INF){mark[node]^=1;swap(Tree[node].maxn,Tree[node].minn);Tree[node].maxn*=-1;Tree[node].minn*=-1;}
 91         else {Tree[node].maxn=Tree[node].minn=toit;}
 92         return ;
 93     }
 94     pushdown(node);
 95     int mid=(l+r)>>1;
 96     cg(l,mid,ls,sa,se,toit);
 97     cg(mid+1,r,rs,sa,se,toit);
 98     updata(node);
 99 }
100 void Change(int x,int y){
101     cg(1,n,1,id[e[x].x],id[e[x].x],y);
102 }
103 void Negdata(int x,int y)
104 {
105     while(top[x]!=top[y]){
106         if(dep[top[x]]<dep[top[y]])swap(x,y);
107         cg(1,n,1,id[top[x]],id[x],INF);
108         x=fa[top[x]];
109     }
110     if(dep[x]<dep[y])swap(x,y);
111     cg(1,n,1,id[y]+1,id[x],INF);
112     return ;
113 }
114 int getsum(int l,int r,int node,int sa,int se)
115 {
116     if(l>se || r<sa)return -INF;
117     if(sa<=l && r<=se)return Tree[node].maxn;
118     pushdown(node);
119     int mid=(l+r)>>1;
120     return max(getsum(l,mid,ls,sa,se),getsum(mid+1,r,rs,sa,se));
121     updata(node);
122 }
123 int Ask(int x,int y)
124 {
125     int ans=-INF,tmp;
126     while(top[x]!=top[y]){
127         if(dep[top[x]]<dep[top[y]])swap(x,y);
128         tmp=getsum(1,n,1,id[top[x]],id[x]);
129         if(tmp>ans)ans=tmp;
130         x=fa[top[x]];
131     }
132     if(dep[x]<dep[y])swap(x,y);
133     tmp=getsum(1,n,1,id[y]+1,id[x]);
134     return max(tmp,ans);
135 }
136 int main()
137 {
138     n=gi();
139     int x,y;
140     for(int i=1;i<n;i++){
141         e[i].x=gi();e[i].y=gi();e[i].z=gi();
142         init(e[i].x,e[i].y,e[i].z);
143     }
144     dep[1]=1;dfs1(1);dfs2(1,1);fa[1]=1;haha[1]=-INF;
145     for(int i=1;i<n;i++){
146         x=e[i].x;y=e[i].y;
147         if(dep[x]<dep[y])swap(x,y),swap(e[i].x,e[i].y);
148         haha[id[x]]=e[i].z;
149     }
150     build(1,n,1);
151     while(1)
152     {
153         scanf("%s%d%d",s,&x,&y);
154         if(s[0]=='D')break;
155         if(s[0]=='C')Change(x,y);
156         else if(s[0]=='N')Negdata(x,y);
157         else if(s[0]=='Q')printf("%d
",Ask(x,y));
158     }
159     return 0;
160 }