[POJ-3237] [Problem E]

Tree

Time Limit: 5000MS		Memory Limit: 131072K
Total Submissions: 13156		Accepted: 3358

题目链接

http://poj.org/problem?id=3237

Description

You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:

`CHANGE` i v	Change the weight of the ith edge to v
`NEGATE` a b	Negate the weight of every edge on the path from a to b
`QUERY` a b	Find the maximum weight of edges on the path from a to b

Input

The input contains multiple test cases. The first line of input contains an integer t (t ≤ 20), the number of test cases. Then follow the test cases.

Each test case is preceded by an empty line. The first nonempty line of its contains N (N ≤ 10,000). The next N − 1 lines each contains three integers a, b and c, describing an edge connecting nodes a and b with weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.

Output

For each “QUERY” instruction, output the result on a separate line.

Sample Input

 

1
​3
1 2 1
2 3 2QUERY 1 2
CHANGE 1 3

QUERY 1 2

DONE

Sample Output

题解

树练剖分的模板题，单点修改，区间查询，还有区间取反（就是变成相反数。。。）。

注意一下单点的lazy标记处理就好了，我是每个区间权值由子区间和lazy标记组成，

然后叶子节点lazy区间用一次就消失。

代码

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 using namespace std;
  6 #define ll long long
  7 #define N 100050
  8 #define INF 0x7f7f7f7f
  9 int n,bh[N],w[N];
 10 struct Tree{int l,r,lazy,max,min;}tr[N<<2];
 11 struct Edge{int from,to,val,id,s;}edges[N<<1];
 12 int tot,last[N];
 13 int cnt,fa[N],size[N],dp[N],son[N],rk[N],kth[N],top[N];
 14 
 15 template<typename T>void read(T&x)
 16 {
 17   ll k=0; char c=getchar();
 18   x=0;
 19   while(!isdigit(c)&&c!=EOF)k^=c=='-',c=getchar();
 20   if (c==EOF)exit(0);
 21   while(isdigit(c))x=x*10+c-'0',c=getchar();
 22   x=k?-x:x;
 23 }
 24 void AddEdge(int x,int y,int z,int id)
 25 {
 26   edges[++tot]=Edge{x,y,z,id,last[x]};
 27   last[x]=tot;
 28 }
 29 void read_char(char &c)
 30 {while(!isalpha(c=getchar())&&c!=EOF);}
 31 void push_up(int x)
 32 {
 33   int len=(tr[x].r-tr[x].l+1);
 34   if (len>1)
 35     {
 36       tr[x].max=max(tr[x<<1].max,tr[x<<1|1].max);
 37       tr[x].min=min(tr[x<<1].min,tr[x<<1|1].min);
 38     }
 39   if (tr[x].lazy==-1)
 40     {
 41       tr[x].max*=-1;
 42       tr[x].min*=-1;
 43       swap(tr[x].max,tr[x].min);
 44     }
 45   if (len==1)tr[x].lazy=1;
 46 }
 47 void push_down(int x)
 48 {
 49   tr[x<<1].lazy*=tr[x].lazy;
 50   tr[x<<1|1].lazy*=tr[x].lazy;
 51   push_up(x<<1);
 52   push_up(x<<1|1);
 53   tr[x].lazy=1;
 54 }
 55 void bt(int x,int l,int r)
 56 {
 57   tr[x].l=l; tr[x].r=r; tr[x].lazy=1;
 58   if (l==r)
 59     {
 60       tr[x].max=tr[x].min=w[kth[l]];
 61       return;
 62     }
 63   int mid=(l+r)>>1;
 64   bt(x<<1,l,mid);
 65   bt(x<<1|1,mid+1,r);
 66   push_up(x);
 67 }
 68 void update(int x,int p,int tt)
 69 {
 70   if (p<=tr[x].l&&tr[x].r<=p)
 71     {
 72       tr[x].max=tr[x].min=tt;
 73       tr[x].lazy=1;
 74       return;
 75     }
 76   int mid=(tr[x].l+tr[x].r)>>1;
 77   push_down(x);
 78   if (p<=mid)update(x<<1,p,tt);
 79   if (mid<p)update(x<<1|1,p,tt);
 80   push_up(x);
 81 }
 82 int neg(int x,int l,int r,int tt)
 83 {
 84   if (l<=tr[x].l&&tr[x].r<=r)
 85     {
 86       tr[x].lazy*=tt;
 87       push_up(x);
 88       return tr[x].max;
 89     }
 90   int mid=(tr[x].l+tr[x].r)>>1,ans=-INF;
 91   push_down(x);
 92   if (l<=mid)ans=max(ans,neg(x<<1,l,r,tt));
 93   if (mid<r)ans=max(ans,neg(x<<1|1,l,r,tt));
 94   push_up(x);
 95   return ans;
 96 }
 97 void dfs1(int x,int pre)
 98 {
 99   fa[x]=pre;
100   dp[x]=dp[pre]+1;
101   size[x]=1;
102   son[x]=0;
103   for(int i=last[x];i;i=edges[i].s)
104     {
105       Edge &e=edges[i];
106       if (e.to==pre)continue;
107       w[e.to]=e.val;
108       bh[e.id]=e.to;
109       dfs1(e.to,x);
110       size[x]+=size[e.to];
111       if (size[e.to]>size[son[x]])son[x]=e.to;
112     }
113 }
114 void dfs2(int x,int y)
115 {
116   rk[x]=++cnt;
117   kth[cnt]=x;
118   top[x]=y;
119   if (son[x]==0)return;
120   dfs2(son[x],y);
121   for(int i=last[x];i;i=edges[i].s)
122     {
123       Edge &e=edges[i];
124       if (e.to==fa[x]||e.to==son[x])continue;
125       dfs2(e.to,e.to);
126     }
127 }
128 int get_max(int x,int y,int tt)
129 {
130   int fx=top[x],fy=top[y],ans=-INF;
131   while(fx!=fy)
132     {
133       if (dp[fx]<dp[fy])swap(x,y),swap(fx,fy);
134       ans=max(ans,neg(1,rk[fx],rk[x],tt));
135       x=fa[fx];fx=top[x];
136     }
137   if (dp[x]<dp[y])swap(x,y);
138   ans=max(ans,neg(1,rk[y]+1,rk[x],tt));
139   return ans;
140 }
141 void work()
142 {
143   read(n);
144   for(int i=1;i<=n-1;i++)
145     {
146       int x,y,z;
147       read(x); read(y); read(z);
148       AddEdge(x,y,z,i);
149       AddEdge(y,x,z,i);
150     }
151   dfs1(1,0);
152   dfs2(1,1);
153   bt(1,1,n);
154   while(1)
155     {
156       char id; int x,y;
157       read_char(id);
158       if (id=='D') break;
159       read(x); read(y);
160       if (id=='C') update(1,rk[bh[x]],y);
161       if (id=='N') get_max(x,y,-1);
162       if (id=='Q') printf("%d
",get_max(x,y,1));
163     }
164 }
165 void clear()
166   {
167     cnt=0; tot=0;
168     memset(last,0,sizeof(last));
169   }
170 int main()
171 {
172 #ifndef ONLINE_JUDGE
173   freopen("aa.in","r",stdin);
174 #endif
175   int q;
176   read(q);
177   while(q--)
178     {
179       clear();
180       work();
181     }
182 }

View Code