作者存档：edward_mj

【题目大意】
给定一棵树，然后给出两种操作：
1、改变某条边的权值
2、询问点x到点y的路径上，长度最长的边的长度是多少？
【算法分析】
我是按照漆子超大神的论文做的。
他如是说道：
对于一棵树，定义Size(u)为以u为根的子树的结点数。
然后对于u与所有儿子v相连的边而言，Size(v)最大的，那条边就叫重边，其它边都是轻边。
Then，有一个重要结论：
每个点到根的路径上都不超过O(lg N)条轻边和O(lg N)条重路径。
（重路径是由重边连续连成的）
然后我们对于每个询问(x,y)的路径，就可以分成(x,lca(x,y))的路径和(y,lca(x,y))的路径。
于是问题变成怎么求x到它一个祖先结点的边权的最大值。
我们就可以轻边直接算，重路径利用线段树求解。
最终就可以在O(Q lg ^2 n)的复杂度得到解。(Q问询问个数)
至于具体实现的话，我是把连续的重边先DFS，然后再DFS其它轻边。
弄一个队列装起来，这样DFS完以后就可以保证连续的重边(重路径)在队列里是连续的。
然后就把连续的重路径涂上同一个颜色。在记录一下这种颜色在队里里起始点是哪。
方便后面利用。
至于求lca我是利用的经典的转化为RMQ求解。
当然，少不了N个指向数组指来指去。。。。，指到头都晕了。

【用到的东西】
LCA——>RMQ
线段树
【其它】
我那叫一个激动啊。。200+行，5KB的程序一次过样例，一次AC！
3552963 2010-04-24 18:16:42 cwj Query on a tree accepted 4.25 6.0M

C++

4.0.0-8

时间有点丑，大概是因为我每次都memset的关系吧。。。
不过能A就成。。。
【CODE】
#include #include #include #define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)<(y)?(x):(y)
const int E=20005;
const int N=10005;
const int INF=1000000000;
struct edge{int x,y,w,next,op,heavy,inlist;}g[E];
struct Node{int l,r,data;}tr[E*5];
int n,Tc,e,heavytot,ctot,rmqtot,ans,nowdep;
int ls[N],Size[N],dep[N],fa[N];
int heavyedge[N],color[E],colorst[E];
int R[E],rmq[16][E],lg[E];

inline void swap(int &x,int &y){x=x^y; y=x^y; x=x^y;}

void addedge(int x,int y,int w){
e++;
g[e].x=x; g[e].y=y; g[e].w=w;
g[e].next=ls[x]; ls[x]=e;
}

void init(){
e=0;
heavytot=0;
ctot=0;
rmqtot=0;
memset(ls,0,sizeof(ls));
memset(heavyedge,0,sizeof(heavyedge));
memset(Size,0,sizeof(Size));
memset(g,0,sizeof(g));
memset(fa,0,sizeof(fa));
memset(color,0,sizeof(color));
memset(colorst,0,sizeof(colorst));
memset(R,0,sizeof(R));
memset(rmq,0,sizeof(rmq));

char op[100];
int x,y,w,i;

scanf("%d",&n);
for (i=1;i scanf("%d%d%d",&x,&y,&w);
addedge(x,y,w);
g[e].op=i+n-1;
}
for (i=1;i addedge(g[i].y,g[i].x,g[i].w);
g[e].op=i;
}
}

void Get_Size(int p,int &times){
rmq[0][++rmqtot]=dep[p];
R[p]=rmqtot;
Size[p]=times++;
for (int t=ls[p];t;t=g[t].next)
if (t!=g[fa[p]].op){
dep[g[t].y]=dep[p]+1;
fa[g[t].y]=t;
Get_Size(g[t].y,times);
rmq[0][++rmqtot]=dep[p];
}
Size[p]=times-Size[p];
}

void Get_heavyedge(int p){
int zz=0,mm=0;
for (int t=ls[p];t;t=g[t].next)
if (t!=g[fa[p]].op && Size[g[t].y]>mm){
mm=Size[g[t].y];
zz=t;
}
if (!zz) return;
heavyedge[++heavytot]=zz;
g[zz].heavy=1;
g[zz].inlist=heavytot;
g[g[zz].op].heavy=1;
g[g[zz].op].inlist=heavytot;
Get_heavyedge(g[zz].y);

for (int t=ls[p];t;t=g[t].next)
if (t!=g[fa[p]].op && t!=zz)
Get_heavyedge(g[t].y);
}

void draw_color(){
ctot=1; color[heavyedge[1]]=1; colorst[1]=1;
for (int i=2;i<=heavytot;i++){
int &t=heavyedge[i],&pt=heavyedge[i-1];
if (g[pt].y!=g[t].x){
ctot++;
colorst[ctot]=i;
}
color[t]=ctot;
color[g[t].op]=ctot;
}
}

void build(int p,int l,int r){
tr[p].l=l; tr[p].r=r;
if (l==r){
tr[p].data=g[heavyedge[l]].w;
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tr[p].data=max(tr[p*2].data,tr[p*2+1].data);
}

void buildrmq(){
int i,k;
lg[1]=0;
for (i=2;i<=rmqtot;i++){
lg[i]=lg[i-1];
if (1< }
for (k=1;(1< for (i=1;i+(1< rmq[k][i]=min(rmq[k-1][i],rmq[k-1][i+(1<}

void pre_work(){
int tmp=0;
dep[1]=1;
fa[1]=0;
Get_Size(1,tmp);
Get_heavyedge(1);
draw_color();
build(1,1,heavytot);
buildrmq();
}

void Change(int p,int pos){
if (tr[p].l==tr[p].r){
tr[p].data=g[heavyedge[pos]].w;
return;
}
int mid=(tr[p].l+tr[p].r)/2;
if (pos<=mid) Change(p*2,pos);
else Change(p*2+1,pos);
tr[p].data=max(tr[p*2].data,tr[p*2+1].data);
}

int getmin(int x,int y){
if (x>y) swap(x,y);
int step=lg[y-x+1];
return min(rmq[step][x],rmq[step][y-(1<}

int getmax(int p,int l,int r){
if (l<=tr[p].l && tr[p].r<=r) return tr[p].data;
int tmp1=-INF,tmp2=-INF,mid=(tr[p].l+tr[p].r)/2;
if (l<=mid) tmp1=getmax(p*2,l,r);
if (r>=mid+1) tmp2=getmax(p*2+1,l,r);
return max(tmp1,tmp2);
}

void Try(int x){
if (dep[x]==nowdep) return;
if (g[fa[x]].heavy){
int &p=g[heavyedge[colorst[color[fa[x]]]]].x,tmp;
if (dep[p]>=nowdep){
Try(p);
tmp=getmax(1,colorst[color[fa[x]]],g[fa[x]].inlist);
ans=max(ans,tmp);
}
else{
tmp=getmax(1,g[fa[x]].inlist-(dep[x]-nowdep-1),g[fa[x]].inlist);
ans=max(ans,tmp);
}
}
else{
Try(g[fa[x]].x);
ans=max(ans,g[fa[x]].w);
}
}

void solve(){
char op[100];
int x,y;
for (;;){
scanf("%s",op+1);
if (op[1]==’D’) return;
if (op[1]==’C’){
scanf("%d%d",&x,&y);
g[x].w=y;
g[g[x].op].w=y;
if (g[x].heavy) Change(1,g[x].inlist);
}
else{
ans=0;
scanf("%d%d",&x,&y);
nowdep=getmin(R[x],R[y]);
Try(x);
Try(y);
printf("%dn",ans);
}
}
}

int main(){
scanf("%d",&Tc);
for (int i=0;i init();
pre_work();
solve();
}
}

【算法分析】
= =，看了解题报告才弄出来。
一开始写了个暴力的最大权闭合图骗分，结果直接崩溃。。。0分。。。Orz，也许是敲错了吧
一开始还以为容斥原理+最小割。。。
该题是动态规划。
首先我们画画图，发现它是楼梯形的。当然，如果两个宝藏y坐标相同，而x坐标差1的话，是可以成一横线的。
然后我们就可以按格子划分状态得到方程：
f[i,j]=max(f[i-1,j-1]+Sum+j,f[i-1][j]+Sum+j,f[i-1][j+1])
然后仅有在宝藏的斜线与y坐标相同的水平线上的状态才是有用的。
于是我们就只搞这些状态就可以了。
处理斜线的话，向上斜的就会x-y为定值，向下斜的就会x+y为定值，然后分别按x-y,x+y，y，排下序，最终就可以利用归并排序的思想，在本x的有效状态数的复杂度内，弄出有效的状态。
然后转移即可。
【CODE】
#include #include using namespace std;
const int N=1005;
const int maxx=10005;
const int E=1000000;
const int INF=100000000;
int n,tot[2],m,ans,X;
int list[2][E],f[2][E];
struct PT{int x,y,p,w;}a[N],b[N],c[N];

int cmp(const void *a,const void *b){
return ((PT*)a)->w-((PT*)b)->w;
}

void input(){
std::ios::sync_with_stdio(false);
tot[0]=0; tot[1]=0;
cin >> n;
for (int i=1;i<=n;i++){
cin >> a[i].x >> a[i].y >> a[i].p;
a[i].y=abs(a[i].y);
}
int ll=1,rr=1;
for (int i=1;i<=n;i++){
ll=min(ll,a[i].x-a[i].y);
rr=max(rr,a[i].x+a[i].y);
}
ll-=5; rr=rr+5-ll;
for (int i=1;i<=n;i++){
a[i].x-=ll;
b[i]=a[i];
c[i]=a[i];
}
X=rr;
for (int i=1;i<=n;i++){
a[i].w=a[i].y;
b[i].w=b[i].x+b[i].y;
c[i].w=c[i].y-c[i].x;
}
qsort(a+1,n,sizeof(PT),cmp);
qsort(b+1,n,sizeof(PT),cmp);
qsort(c+1,n,sizeof(PT),cmp);
}

void build(int x,int &tot,int *list,int *f){
tot=1;
list[1]=0;
f[1]=0; f[2]=f[3]=f[4]=-INF;
int t1=1,t2=1,t3=1,now,pos;
while (t1<=n || t2<=n || t3<=n){
now=INF; pos=0;
if (t1<=n && a[t1].w if (t2<=n && b[t2].w-x if (t3<=n && c[t3].w+x switch (pos){
case 0:for (;;);
case 1:
if (a[t1].w !=list[tot]) list[++tot]=a[t1].w;
t1++;
break;
case 2:
if (b[t2].w-x!=list[tot] && b[t2].w-x>=0) list[++tot]=b[t2].w-x;
t2++;
break;
case 3:
if (c[t3].w+x!=list[tot] && c[t3].w+x>=0) list[++tot]=c[t3].w+x;
t3++;
break;
}
}
}

void dp(int x,int &pt,int &nt,int *pl,int *nl,int *pf,int *f){
int i,j=1,k=1,Sum=0,jj;
for (i=1;i<=nt;i++){
while (k<=n && a[k].y<=nl[i]){
if (a[k].x==x) Sum+=a[k].p;
k++;
}
while (j<=pt && pl[j]+1 f[i]=-INF;
for (jj=j;jj<=j+3 && jj<=pt;jj++)
if (abs(pl[jj]-nl[i])<=1)
f[i]=max(f[i],pf[jj]+Sum-nl[i]);
}
f[1]=max(0,f[1]);
ans=max(ans,f[1]);
}

void work(){
ans=0; f[0][0]=f[0][2]=-INF;
tot[0]=1; list[0][1]=0; f[0][1]=0;
for (int i=1;i<=X;i++){
build(i,tot[i%2],list[i%2],f[i%2]);
dp(i,tot[1-i%2],tot[i%2],list[1-i%2],list[i%2],f[1-i%2],f[i%2]);
}
}

int main(){
freopen("treasures.in","r",stdin);
freopen("treasures.out","w",stdout);
input();
work();
cout << ans << endl;
return 0;
}