| 记录编号 |
146636 |
评测结果 |
TTTTTTTTTT |
| 题目名称 |
[国家集训队2011]旅游 |
最终得分 |
0 |
| 用户昵称 |
 MINE·MINE |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
10.000 s |
| 提交时间 |
2015-01-18 16:21:13 |
内存使用 |
18.81 MiB |
显示代码纯文本
#include<cstdio>
#include<vector>
using namespace std;
inline int MAX(int a,int b)
{
if(a>b) return a;
return b;
}
inline int MIN(int a,int b)
{
if(a<b) return a;
return b;
}
inline void SWAP(int &a,int &b)
{
int c=b;
a=b,b=c;
}
const int Size=200001;
inline void readQ(int &rec)
{
char ret; bool flag=false; rec=0;
while(ret=getchar(),ret<'!');
if(ret=='-') flag=true,ret=getchar();
while(rec=rec*10+ret-'0',ret=getchar(),ret>'!');
if(flag) rec=-rec;
}
int N,M;
vector<int> Net[Size];
int father[Size],heavy[Size],top[Size];
int rank[Size],New=0,Edge[Size][3],deepth[Size],tot[Size];
bool flag[Size];
int Max[Size<<2],Sum[Size<<2],Min[Size<<2];
inline void DFS(int,int);
inline void Cut(int,int);
inline void Build(int,int,int);
inline void Inject(int,int,int,int,int);
inline void LTchange(int,int,int,int,int);
inline void Minus(int,int);
inline void LTneg(int,int,int,int,int);
inline int findMax(int,int);
inline int LTfindMax(int,int,int,int,int);
inline int findMin(int,int);
inline int LTfindMin(int,int,int,int,int);
inline int findSum(int,int);
inline int LTfindSum(int,int,int,int,int);
int main()
{
freopen("nt2011_travel.in","r",stdin);
freopen("nt2011_travel.out","w",stdout);
//freopen("test.in","r",stdin);
readQ(N);
int i,a,b; char order[6];
for(i=1;i<N;i++)
{
readQ(Edge[i][0]),readQ(Edge[i][1]),readQ(Edge[i][2]);
Edge[i][0]++,Edge[i][1]++;
Net[Edge[i][0]].push_back(Edge[i][1]);
Net[Edge[i][1]].push_back(Edge[i][0]);
}
for(i=1;i<=N;i++)
heavy[i]=father[i]=top[i]=0,tot[i]=1;
DFS(1,1);
Cut(1,1);
Build(1,1,N);
for(i=1;i<N;i++)
{
if(deepth[Edge[i][0]]>deepth[Edge[i][1]])
SWAP(Edge[i][0],Edge[i][1]);
Inject(1,1,N,rank[Edge[i][1]],Edge[i][2]);
}
readQ(M);
for(i=1;i<=M;i++)
{
scanf("%s",order);
readQ(a),readQ(b);
if(order[0]=='C')
{
LTchange(1,1,N,rank[Edge[a][1]],b);
}
else
{
a++,b++;
if(order[0]=='N')
Minus(a,b);
else
{
if(order[0]=='M')
{
if(order[1]=='A')
printf("%d\n",findMax(a,b));
else
printf("%d\n",findMin(a,b));
}
else
printf("%d\n",findSum(a,b));
}
}
}
return 0;
}
inline void DFS(int x,int d)
{
flag[x]=true,deepth[x]=d;
for(int i=0;i<Net[x].size();i++)
{
if(!flag[Net[x][i]])
{
flag[Net[x][i]]=true;
father[Net[x][i]]=x;
DFS(Net[x][i],d+1);
if(!heavy[x]||tot[heavy[x]]<tot[Net[x][i]])
heavy[x]=Net[x][i];
tot[x]+=tot[Net[x][i]];
}
}
}
inline void Cut(int x,int y)
{
rank[x]=++New,top[x]=y;
if(heavy[x]) Cut(heavy[x],y);
for(int i=0;i<Net[x].size();i++)
{
if(Net[x][i]!=father[x]&&Net[x][i]!=heavy[x])
Cut(Net[x][i],Net[x][i]);
}
}
inline void Build(int x,int l,int r)
{
if(l==r)
{
Max[x]=Sum[x]=0;
Min[x]=0x3f3f3f3f;
return ;
}
int m=(l+r)>>1;
Build(x<<1,l,m),Build(x<<1|1,m+1,r);
}
inline void Inject(int x,int l,int r,int o,int d)
{
if(l==r)
{
Max[x]=Sum[x]=Min[x]=d;
return ;
}
int m=(l+r)>>1;
if(o<=m) Inject(x<<1,l,m,o,d);
else Inject(x<<1|1,m+1,r,o,d);
Max[x]=MAX(Max[x<<1],Max[x<<1|1]);
Min[x]=MIN(Min[x<<1],Min[x<<1|1]);
Sum[x]=Sum[x<<1]+Sum[x<<1|1];
}
inline void Minus(int x,int y)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(deepth[fx]<deepth[fy])
SWAP(fx,fy),SWAP(x,y);
LTneg(1,1,N,rank[fx],rank[x]);
x=father[fx],fx=top[x];
}
if(deepth[x]>deepth[y])
SWAP(x,y);
LTneg(1,1,N,rank[heavy[x]],rank[y]);
}
inline void LTneg(int x,int l,int r,int qx,int qy)
{
if(l==r)
{
Max[x]=-Max[x],Sum[x]=-Sum[x],Min[x]=-Min[x];
return ;
}
int m=(l+r)>>1;
if(qx<=m) LTneg(x<<1,l,m,qx,qy);
if(qy>m) LTneg(x<<1|1,m+1,r,qx,qy);
Max[x]=MAX(Max[x<<1],Max[x<<1|1]);
Min[x]=MIN(Min[x<<1],Min[x<<1|1]);
Sum[x]=Sum[x<<1]+Sum[x<<1|1];
}
inline void LTchange(int x,int l,int r,int o,int d)
{
if(l==r)
{
Max[x]=Sum[x]=Min[x]=d;
return ;
}
int m=(l+r)>>1;
if(o <=m) LTchange(x<<1,l,m,o,d);
else LTchange(x<<1|1,m+1,r,o,d);
Max[x]=MAX(Max[x<<1],Max[x<<1|1]);
Min[x]=MIN(Min[x<<1],Min[x<<1|1]);
Sum[x]=Sum[x<<1]+Sum[x<<1|1];
}
inline int findMax(int x,int y)
{
int fx=top[x],fy=top[y],temp=-0x3f3f3f3f;
while(fx!=fy)
{
if(deepth[fx]<deepth[fy])
SWAP(fx,fy),SWAP(x,y);
temp=MAX(temp,LTfindMax(1,1,N,rank[fx],rank[x]));
x=father[fx],fx=top[x];
}
if(deepth[x]>deepth[y])
SWAP(x,y);
temp=MAX(temp,LTfindMax(1,1,N,rank[heavy[x]],rank[y]));
return temp;
}
inline int LTfindMax(int x,int l,int r,int qx,int qy)
{
if(l==r)
return Max[x];
int m=(l+r)>>1,temp=-0x3f3f3f3f;
if(qx<=m) temp=MAX(temp,LTfindMax(x<<1,l,m,qx,qy));
if(qy>m) temp=MAX(temp,LTfindMax(x<<1|1,m+1,r,qx,qy));
return temp;
}
inline int findMin(int x,int y)
{
int fx=top[x],fy=top[y],temp=0x3f3f3f3f;
while(fx!=fy)
{
if(deepth[fx]<deepth[fy])
SWAP(fx,fy),SWAP(x,y);
temp=MIN(temp,LTfindMin(1,1,N,rank[fx],rank[x]));
x=father[fx],fx=top[x];
}
if(deepth[x]>deepth[y])
SWAP(x,y);
temp=MIN(temp,LTfindMin(1,1,N,rank[heavy[x]],rank[y]));
return temp;
}
inline int LTfindMin(int x,int l,int r,int qx,int qy)
{
if(l==r)
return Min[x];
int m=(l+r)>>1,temp=0x3f3f3f3f;
if(qx<=m) temp=MIN(temp,LTfindMin(x<<1,l,m,qx,qy));
if(qy>m) temp=MIN(temp,LTfindMin(x<<1|1,m+1,r,qx,qy));
return temp;
}
inline int findSum(int x,int y)
{
int fx=top[x],fy=top[y],temp=0;
while(fx!=fy)
{
if(deepth[fx]<deepth[fy])
SWAP(fx,fy),SWAP(x,y);
temp+=LTfindSum(1,1,N,rank[fx],rank[x]);
x=father[fx],fx=top[x];
}
if(deepth[x]>deepth[y])
SWAP(x,y);
temp+=LTfindSum(1,1,N,rank[heavy[x]],rank[y]);
return temp;
}
inline int LTfindSum(int x,int l,int r,int qx,int qy)
{
if(l==r)
return Sum[x];
int m=(l+r)>>1,temp=0;
if(qx<=m) temp+=LTfindSum(x<<1,l,m,qx,qy);
if(qy>m) temp+=LTfindSum(x<<1|1,m+1,r,qx,qy);
return temp;
}