myx12345's Blog

2等狗表示知识的范围已经被拉开了。

T1:结论题。2^nk 

我不想说什么，刚开始在这题上荒废了1H。

最后爆搜打表找规律绝杀。

码都不想放了。

T2、T3 AC后补。

大爷们这次异常萎靡。

140，居然仅次于ZYD(220),niroBC(230),和双国一叶爷爷(220)。

很多人T1没打出来。

罗爷爷T3正解写错了（然而我不会正解）。

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身

我觉得作为我刷的第一道树链剖分作为模板还是要补一下题解的。

线段树上的操作没什么好说的，主要是query_max和query_sum

比如说我们要求x,y中间路径上的和

我们比较top[x],top[y]即f1,f2的深度

选比较大的那个

取出tid[f1]与tid[x]上的信息

然后x=fa[f1]向上找另一条重链

做到f1=f2为止

最后还有[x,y]的

恩大概就是这样了

那么

var a,head,vet,next,fa,dep,size,flag,tid,son,top,pre,    
    tree_max,tree_sum,isok:array[1..400010]of longint;
    ch:string;
    x,y,n,i,m,j,len,tot,time:longint;
 
procedure swap(var x,y:longint);
var t:longint;
begin
 t:=x; x:=y; y:=t;
end;
 
procedure add(a,b:longint);
begin
 inc(tot);
 next[tot]:=head[a];
 vet[tot]:=b;
 head[a]:=tot;
end;
 
procedure dfs1(u,father,depth:longint);
var e,v,maxsize:longint;
begin
 fa[u]:=father; dep[u]:=depth;
 size[u]:=1; maxsize:=0; son[u]:=0;
 flag[u]:=1;
 e:=head[u];
 while e<>0 do
 begin
  v:=vet[e];
  if flag[v]=0 then
  begin
   isok[e]:=1;
   dfs1(v,u,depth+1);
   size[u]:=size[u]+size[v];
   if size[v]>maxsize then
   begin
    maxsize:=size[v];
    son[u]:=v;
   end;
  end;
  e:=next[e];
 end;
end;
 
procedure dfs2(u,ance:longint);
var e,v:longint;
begin
 inc(time); tid[u]:=time; pre[time]:=u; top[u]:=ance;
 flag[u]:=1;
 if son[u]<>0 then dfs2(son[u],ance);
 e:=head[u];
 while e<>0 do
 begin
  v:=vet[e];
  if (isok[e]=1)and(flag[v]=0) then dfs2(v,v);
  e:=next[e];
 end;
end;
 
function max(x,y:longint):longint;
begin
 if x>y then exit(x);
 exit(y);
end;
 
procedure build(l,r,p:longint);
var mid:longint;
begin
 if l=r then
 begin
  tree_sum[p]:=a[pre[l]];
  tree_max[p]:=a[pre[l]];
  exit;
 end;
 mid:=(l+r)>>1;
 build(l,mid,p<<1);
 build(mid+1,r,p<<1+1);
 tree_sum[p]:=tree_sum[p<<1]+tree_sum[p<<1+1];
 tree_max[p]:=max(tree_max[p<<1],tree_max[p<<1+1]);
end;
 
procedure update(l,r,x,v,p:longint);
var mid:longint;
begin
 if l=r then
 begin
  tree_sum[p]:=v;
  tree_max[p]:=v;
  exit;
 end;
 mid:=(l+r)>>1;
 if x<=mid then update(l,mid,x,v,p<<1);
 if x>mid then update(mid+1,r,x,v,p<<1+1);
 tree_sum[p]:=tree_sum[p<<1]+tree_sum[p<<1+1];
 tree_max[p]:=max(tree_max[p<<1],tree_max[p<<1+1]);
end;
 
function search_max(l,r,x,y,p:longint):longint;
var mid:longint;
begin
 if (l=x)and(r=y) then exit(tree_max[p]);
 mid:=(l+r)>>1;
 if y<=mid then exit(search_max(l,mid,x,y,p<<1))
  else if x>mid then exit(search_max(mid+1,r,x,y,p<<1+1))
   else exit(max(search_max(l,mid,x,mid,p<<1),
                 search_max(mid+1,r,mid+1,y,p<<1+1)));
end;
 
function search_sum(l,r,x,y,p:longint):longint;
var mid:longint;
begin
 if (l=x)and(r=y) then exit(tree_sum[p]);
 mid:=(l+r)>>1;
 if y<=mid then exit(search_sum(l,mid,x,y,p<<1))
  else if x>mid then exit(search_sum(mid+1,r,x,y,p<<1+1))
   else exit(search_sum(l,mid,x,mid,p<<1)+
             search_sum(mid+1,r,mid+1,y,p<<1+1));
end;
 
function query_max(x,y:longint):longint;
var f1,f2,t,ans:longint;
begin
 f1:=top[x]; f2:=top[y]; ans:=-maxlongint div 3;
 while f1<>f2 do
 begin
  if dep[f1]<dep[f2] then
  begin
   t:=f1; f1:=f2; f2:=t;
   t:=x; x:=y; y:=t;
  end;
  ans:=max(ans,search_max(1,n,tid[f1],tid[x],1));
  x:=fa[f1]; f1:=top[x];
 end;
 if dep[x]>dep[y] then ans:=max(ans,search_max(1,n,tid[y],tid[x],1))
  else ans:=max(ans,search_max(1,n,tid[x],tid[y],1));
 exit(ans);
end;
 
function query_sum(x,y:longint):longint;
var f1,f2,ans,t:longint;
begin
 f1:=top[x]; f2:=top[y]; ans:=0;
 while f1<>f2 do
 begin
  if dep[f1]<dep[f2] then
  begin
   t:=f1; f1:=f2; f2:=t;
   t:=x; x:=y; y:=t;
  end;
  ans:=ans+search_sum(1,n,tid[f1],tid[x],1);
  x:=fa[f1]; f1:=top[x];
 end;
 if dep[x]>dep[y] then ans:=ans+search_sum(1,n,tid[y],tid[x],1)
  else ans:=ans+search_sum(1,n,tid[x],tid[y],1);
 //exit(ans);
end;
 
begin
 
 readln(n);
 for i:=1 to n-1 do
 begin
  readln(x,y);
  add(x,y);
  add(y,x);
 end;
 for i:=1 to n do read(a[i]);
 readln;
 dfs1(1,-1,1);
 fillchar(flag,sizeof(flag),0);
 dfs2(1,1);
 fillchar(tree_max,sizeof(tree_max),$8f);
 build(1,n,1);
 readln(m);
 for i:=1 to m do
 begin
  readln(ch); len:=length(ch);
  x:=0; y:=0;
  if ch[1]='C' then
  begin
   delete(ch,1,7);
   val(copy(ch,1,pos(' ',ch)-1),x);
   val(copy(ch,pos(' ',ch)+1,length(ch)-pos(' ',ch)),y);
   update(1,n,tid[x],y,1);
  end
   else if ch[2]='M' then
   begin
    delete(ch,1,5);
    val(copy(ch,1,pos(' ',ch)-1),x);
    val(copy(ch,pos(' ',ch)+1,length(ch)-pos(' ',ch)),y);
    writeln(query_max(x,y));
   end
    else
    begin
     delete(ch,1,5);
     val(copy(ch,1,pos(' ',ch)-1),x);
     val(copy(ch,pos(' ',ch)+1,length(ch)-pos(' ',ch)),y);
     writeln(query_sum(x,y));
 
    end;
 end;
 
end.

 有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个

这是我A的第二道树链剖分，A第一道在4个月前。

http://blog.sina.com.cn/s/blog_7a1746820100wp67.html

http://www.tuicool.com/articles/mQB36z

这俩教程不错。

因为以X为根中的子树分成了一条条重链，而他们的编号是连续的。

所以我们可以在DFS2时找到以x为根时它的子树在线段树中的最大编号mx[x]。

然后就是裸地区间修改和求和。

这LCA都不用。

记得大数据题要写成t[p].s:=t[p].s*(r-l+1)*v，v:int64（WA*N）

var t:array[1..500000]of record
                             a,s:int64;
                            end;
    head,vet,next,top,tid,mx,fa,size,a:array[0..200000]of longint;
    n,m,i,x,y,tot,time,ch:longint;

procedure add(a,b:longint);
begin
 inc(tot);
 next[tot]:=head[a];
 vet[tot]:=b;
 head[a]:=tot;
end;

function max(x,y:longint):longint;
begin
 if x>y then exit(x);
 exit(y);
end;

function min(x,y:longint):longint;
begin
 if x<y then exit(X);
 exit(y);
end;

procedure dfs1(u:longint);
var e,v:longint;
begin
 size[u]:=1;
 e:=head[u];
 while e<>0 do
 begin
  v:=vet[e];
  if v<>fa[u] then
  begin
   fa[v]:=u;
   dfs1(v);
   size[u]:=size[u]+size[v];
   mx[u]:=max(mx[u],mx[v]);
  end;
  e:=next[e];
 end;
end;

procedure dfs2(u,ance:longint);
var e,v,k:longint;
begin
 inc(time); tid[u]:=time; top[u]:=ance; mx[u]:=time;
 e:=head[u];
 k:=0;
 while e<>0 do
 begin
  v:=vet[e];
  if (v<>fa[u])and(size[v]>size[k]) then k:=v;
  e:=next[e];
 end;
 if k>0 then
 begin
  dfs2(k,ance);
  mx[u]:=max(mx[u],mx[k]);
 end;
 e:=head[u];
 while e<>0 do
 begin
  v:=vet[e];
  if (v<>fa[u])and(v<>k) then
  begin
   dfs2(v,v);
   mx[u]:=max(mx[u],mx[v]);
  end;
  e:=next[e];
 end;
end;

procedure pushdown(l,r,p:longint);
var mid,ls,rs:longint;
begin
 if l=r then exit;
 mid:=(l+r)>>1;
 ls:=p<<1; rs:=ls+1;
 t[ls].a:=t[ls].a+t[p].a;
 t[rs].a:=t[rs].a+t[p].a;
 t[ls].s:=t[ls].s+(mid-l+1)*t[p].a;
 t[rs].s:=t[rs].s+(r-mid)*t[p].a;
 t[p].a:=0;
end;

function query(l,r,x,y,p:longint):int64;
var mid:longint;
begin
 if (l>=x)and(r<=y) then exit(t[p].s);
 pushdown(l,r,p);
 mid:=(l+r)>>1;
 query:=0;
 if x<=mid then query:=query+query(l,mid,x,y,p<<1);
 if y>mid then query:=query+query(mid+1,r,x,y,p<<1+1);
end;

function querys(x:longint):int64;
begin
 querys:=0;
 while top[x]<>1 do
 begin
  querys:=querys+query(1,n,tid[top[x]],tid[x],1);
  x:=fa[top[x]];
 end;
 querys:=querys+query(1,n,1,tid[x],1);
end;

procedure update(l,r,x,y:longint;v:int64;p:longint);
var mid:longint;
begin
 if (l>=x)and(r<=y) then
 begin
  t[p].a:=t[p].a+v;
  t[p].s:=t[p].s+v*(r-l+1);
  exit;
 end;
 pushdown(l,r,p);
 mid:=(l+r)>>1;
 if x<=mid then update(l,mid,x,y,v,p<<1);
 if y>mid then update(mid+1,r,x,y,v,p<<1+1);
 t[p].s:=t[p<<1].s+t[p<<1+1].s;
end;


begin
 assign(input,'1.in'); reset(input);
 assign(output,'1.out'); rewrite(output);
 read(n,m);
 for i:=1 to n do read(a[i]);
 for i:=1 to n-1 do
 begin
  read(x,y);
  add(x,y);
  add(y,x);
 end;
 dfs1(1);
 dfs2(1,1);
 for i:=1 to n do update(1,n,tid[i],tid[i],a[i],1);

 for i:=1 to m do
 begin
  read(ch);
  case ch of
   1:
   begin
    read(x,y);
    update(1,n,tid[x],tid[x],y,1);
   end;
   2:
   begin
    read(x,y);
    update(1,n,tid[x],mx[x],y,1);
   end;
   3:
   begin
    read(x);
    writeln(querys(x));
   end;
  end;
 end;

 close(input);
 close(output);
end.

JSTSC DAY1 T2 已经弃疗

但也不能一直颓一个晚上。

那么我们来找点事情做。

这题看起来不错，过了这么长时间有10000000人过了。一定是道水题。题面上还有d(x,y)这么熟悉的距离，还是棵树。好了就是你了。

0.5小时后：这样应该差不多了。

0.75小时(WA*n)后：日。

1小时(AC)：呵呵。

题意：

n个点，n-1条边的树，有边权值。

任意选出三个点建城市，其花费是dis（a,b）+ dis（a,c）+ dis(b,c);

有q个询问，每次改变一条边的长度，求出所有建城市的方案的花费期望。

思路：

这题与罗爷爷在某场BC中绝杀的T3差不多(%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%）。取点的方案有C(n,3 )。

考虑每条边对结果的贡献。

假设我们有这样一棵树。

我们将其剖分。

剖出来x个点。

那么它对答案有多少贡献？我不会算。

不过我们可以猜出大概是这样一个东西：经过的次数=(x*(x-1)*y+y*(y-1)*x)*c

c是什么？一个常数。是多少？我不知道。

给你样例干嘛？让你凑的。常数就那几个，你1，*2/2*4/4*6/6 /c(n,3)都试试。

试出来是1/c(n,3)。

那么我们就可以做了。

答案怎么算都告诉你了代码就不贴了。

作为一只2=狗能继续在这里做题还是很开心的。

T1：给定一颗有点权的树，每个树上的节点最多能走到lim[u]次，求一条路径，使路径上的点权和最大，每个节点上的点权如果走了多次只能算一次。还要求方案是否唯一。

第一眼：SPFA 的松弛次数限制？（因为树的条件只在input里面）

第二眼：我擦第一问这不是原题么。快乐排序。绝逼有很多人要写成n2 logn。

第三眼：我擦第二问日了狗了。

题解：每个点只能取lim[u]-1个子树。因为每个子树只取1次或不取，考虑树形DP,dp[u]=dp[v1]+dp[v2]+...（加lim[u]-1）个，是排序后最大的。因为不一定要去满lim[u]-1个,如果负数就不走。

判多解：

1.儿子不唯一老子不唯一。

2.取得最后一个和不取的第一个dp值相等就不唯一。

3.取得里面有0就不唯一。(考试时死在这里。）

T2.真的不想说什么。唯一的贡献就是让我学会了矩阵哈希的正确姿势。

for i:=1 to n do

T3.定义题。做法请看题目。

删除假节点并连边：先按输入构图并统计每个点的度数 找一个度不为2的点做一遍dfs

if d[v]=2 f[find(u)]=f[find(v)]

做完之后重连所有f[x[i]]<>f[y[i]]的边

同构：

哈希，将点上的哈希初值都=1，对于点u，取与u相连的点权V并排序，随意哈希作为新的哈希值。迭代10000000000000000000000000000000次。最后只需判断哈希值是否相等。