Tree
Time Limit: 5000MS
Memory Limit: 131072K
Total Submissions: 6131
Accepted: 1682
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 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
Sample Output
1
3
Source
POJ Monthly--2007.06.03, Lei, Tao
題目大意：一棵樹query查詢a到b最大值，change 修改第a條邊權值變成b，NEGATE a到b的所有權值變為相反數
ac代碼
Problem: 3237 User: kxh1995
Memory: 3096K Time: 657MS
Language: C++ Result: Accepted
#include
#include
#include
#include
#include
#include
#define INF 0x7fffffff
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?b:a)
using namespace std;
int vis[100500];
struct LCT
{
int bef[100050],pre[100050],next[100050][2],key[100050],val[100050],belong[100010],maxn[100010],minn[100010],neg[100010];
void init()
{
memset(pre,0,sizeof(pre));
memset(next,0,sizeof(next));
//memset(key,0,sizeof(key));
memset(neg,0,sizeof(neg));
maxn[0]=-INF;
minn[0]=INF;
}
void pushup(int x)
{
maxn[x]=key[x];
minn[x]=key[x];
if(next[x][0])
{
maxn[x]=max(maxn[x],maxn[next[x][0]]);
minn[x]=min(minn[x],minn[next[x][0]]);
}
if(next[x][1])
{
maxn[x]=max(maxn[x],maxn[next[x][1]]);
minn[x]=min(minn[x],minn[next[x][1]]);
}
}
void Not(int x)
{
if(x)
{
neg[x]^=1;
swap(minn[x],maxn[x]);
key[x]=-key[x];
minn[x]=-minn[x];
maxn[x]=-maxn[x];
}
}
void pushdown(int x)
{
if(neg[x])
{
Not(next[x][0]);
Not(next[x][1]);
neg[x]=0;
}
}
void rotate(int x,int kind)
{
int y,z;
y=pre[x];
z=pre[y];
pushdown(y);
pushdown(x);
next[y][!kind]=next[x][kind];
pre[next[x][kind]]=y;
next[z][next[z][1]==y]=x;
pre[x]=z;
next[x][kind]=y;
pre[y]=x;
pushup(y);
}
void splay(int x)
{
int rt;
for(rt=x;pre[rt];rt=pre[rt]);
if(x!=rt)
{
bef[x]=bef[rt];
bef[rt]=0;
pushdown(x);
while(pre[x])
{
if(next[pre[x]][0]==x)
{
rotate(x,1);
}
else
rotate(x,0);
}
pushup(x);
}
}
void access(int x)
{
int fa;
for(fa=0;x;x=bef[x])
{
splay(x);
pushdown(x);
pre[next[x][1]]=0;
bef[next[x][1]]=x;
next[x][1]=fa;
pre[fa]=x;
bef[fa]=0;
fa=x;
pushup(x);
}
}
void change(int x,int y)
{
int t=belong[x-1];
splay(t);
key[t]=y;
}
int negate(int x,int y)
{
access(y);
for(y=0;x;x=bef[x])
{
splay(x);
if(!bef[x])
{
Not(y);
Not(next[x][1]);
return 1;
}
pushdown(x);
pre[next[x][1]]=0;
bef[next[x][1]]=x;
next[x][1]=y;
pre[y]=x;
bef[y]=0;
y=x;
pushup(x);
}
return 0;
}
int query(int x,int y)
{
access(y);
for(y=0;x;x=bef[x])
{
splay(x);
if(!bef[x])
{
return max(maxn[y],maxn[next[x][1]]);
}
pushdown(x);
pre[next[x][1]]=0;
bef[next[x][1]]=x;
next[x][1]=y;
pre[y]=x;
bef[y]=0;
y=x;
pushup(x);
}
return 0;
}
}lct;
int head[100010],cnt;
struct s
{
int u,v,w,next;
}edge[100010<<1];
void add(int u,int v,int w)
{
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void bfs(int u)
{
queueq;
memset(vis,0,sizeof(vis));
vis[u]=1;
q.push(u);
while(!q.empty())
{
u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(!vis[v])
{
lct.bef[v]=u;
lct.key[v]=edge[i].w;
lct.belong[i>>1]=v;
vis[v]=1;
q.push(v);
}
}
}
}
int main()
{
int t;
scanf(%d,&t);
while(t--)
{
int n;
scanf(%d,&n);
memset(head,-1,sizeof(head));
cnt=0;
for(int i=1;i
