树形结构升级版

A树的直径（模板）

Given a tree (a connected graph with no cycles), you have to find the farthest nodes in the tree. The edges of the tree are weighted and undirected. That means you have to find two nodes in the tree whose distance is maximum amongst all nodes.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with an integer n (2 ≤ n ≤ 30000) denoting the total number of nodes in the tree. The nodes are numbered from 0 to n-1. Each of the next n-1 lines will contain three integers u v w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 10000)denoting that node u and v are connected by an edge whose weight is w. You can assume that the input will form a valid tree.

Output

For each case, print the case number and the maximum distance.

Sample Input

2

4

0 1 20

1 2 30

2 3 50

5

0 2 20

2 1 10

0 3 29

0 4 50

Sample Output

Case 1: 100

Case 2: 80

var
t,n,m,i,j,x,y,z,e,po,l:longint;
max:int64;
head,next,a,dis,w:array[-100..600005]of longint;
procedure add(x,y,z:longint);
begin
 inc(e); a[e]:=y; next[e]:=head[x];head[x]:=e; w[e]:=z;
end;
procedure dfs(u,m:longint);
 var i,v:longint;
 begin
  i:=head[u];
  while i>0 do
   begin
     v:=a[i];
     if v<>m then
      begin
       if dis[u]+w[i]>dis[v] then dis[v]:=dis[u]+w[i];

         if dis[v]>max then
        begin
          max:=dis[v];
          po:=v;
       end;
        dfs(v,u);//you wrong
       end;
      i:=next[i];
   end;
 end;
begin
readln(T);
for l:=1 to t do
begin
fillchar(head,sizeof(head),0);
 fillchar(next,sizeof(next),0);
 fillchar(a,sizeof(a),255);
 fillchar(w,sizeof(w),0);
  fillchar(dis,sizeof(dis),0);
  readln(n);
  e:=0;  dis[0]:=0;max:=0; po:=0;
  for i:=1 to n-1 do
   begin
     readln(x,y,z);
     add(x,y,z);
     add(y,x,z);
   end;
  dfs(0,0);
  fillchar(dis,sizeof(dis),0);//一定要再次清0！
  dfs(po,po);
 writeln('Case ',l,': ',max);
end;
end. 

B - 树的重心（模板）

Last years Chicago was full of gangster fights and strange murders. The chief of the police got really tired of all these crimes, and decided to arrest the mafia leaders.

Unfortunately, the structure of Chicago mafia is rather complicated. There are npersons known to be related to mafia. The police have traced their activity for some time, and know that some of them are communicating with each other. Based on the data collected, the chief of the police suggests that the mafia hierarchy can be represented as a tree. The head of the mafia, Godfather, is the root of the tree, and if some person is represented by a node in the tree, its direct subordinates are represented by the children of that node. For the purpose of conspiracy the gangsters only communicate with their direct subordinates and their direct master.

Unfortunately, though the police know gangsters’ communications, they do not know who is a master in any pair of communicating persons. Thus they only have an undirected tree of communications, and do not know who Godfather is.

Based on the idea that Godfather wants to have the most possible control over mafia, the chief of the police has made a suggestion that Godfather is such a person that after deleting it from the communications tree the size of the largest remaining connected component is as small as possible. Help the police to find all potential Godfathers and they will arrest them.

Input

The first line of the input file contains n — the number of persons suspected to belong to mafia (2 ≤ n ≤ 50 000). Let them be numbered from 1 to n.

The following n − 1 lines contain two integer numbers each. The pair a_i, b_i means that the gangster a_i has communicated with the gangster b_i. It is guaranteed that the gangsters’ communications form a tree.

Output

Print the numbers of all persons that are suspected to be Godfather. The numbers must be printed in the increasing order, separated by spaces.

Sample Input

6
1 2
2 3
2 5
3 4
3 6

Sample Output

2 3
题意：就是让你求出所有重心啦
题解：在做完这题之后我意识到一个很不得了的事情——在循环中（或dfs）中多次使用fillchar，，，会超时！因为这个东西只是代替了for循环（可能快一点），而且它for的边界是你的数组大小
这就很容易超时了。另外在这一题中，你需要知道树重心的一个性质，一颗树最多只有两个重心，所以在求重心的时候你只需要开两个变量就行了，不需要开数组，这可能也会超时。

var
e,n,i,j,x,y,ans,tot,t,tot1,tot2:longint;
size,head,next,son,a:array[0..300005]of longint;
procedure add(x,y:longint);
 begin
  inc(e);a[e]:=y;next[e]:=head[x];head[x]:=e;
 end;
 function max(x,y:longint):longint;
  begin
    if x>y then exit(x) else exit(y);
  end;
procedure  dfs(u,m:longint);
var v,i,k,tem:longint;
begin
tem:=0;
 i:=head[u];
 while i>0 do
  begin
   v:=a[i];
   if v<>m then
    begin
      dfs(v,u);
      son[u]:=son[u]+son[v]+1;
      tem:=max(tem,son[v]+1);
    end;
   i:=next[i];
  end;
  k:=max(tem,n-son[u]-1);
  if k<ans then
    begin
     tot2:=0;
     tot1:=u;
     ans:=k;
    end
     else
     if k=ans then
      begin
        tot2:=u;
      end;
end;
begin
 readln(n);
 ans:=1<<30;
 for i:=1 to n-1 do
  begin
   readln(x,y);
   add(x,y);
   add(y,x);
  end;
  dfs(1,1);
  if (tot2<>0)and(tot1>tot2) then begin t:=tot1;tot1:=tot2;tot2:=t;end;
   if tot2=0 then writeln(tot1)
   else writeln(tot1,' ',tot2);
end.

C - Fools and Roads

They say that Berland has exactly two problems, fools and roads. Besides, Berland has n cities, populated by the fools and connected by the roads. All Berland roads are bidirectional. As there are many fools in Berland, between each pair of cities there is a path (or else the fools would get upset). Also, between each pair of cities there is no more than one simple path (or else the fools would get lost).

But that is not the end of Berland's special features. In this country fools sometimes visit each other and thus spoil the roads. The fools aren't very smart, so they always use only the simple paths.

A simple path is the path which goes through every Berland city not more than once.

The Berland government knows the paths which the fools use. Help the government count for each road, how many distinct fools can go on it.

Note how the fools' paths are given in the input.

Input

The first line contains a single integer n (2 ≤ n ≤ 10⁵) — the number of cities.

Each of the next n - 1 lines contains two space-separated integers u_i, v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i), that means that there is a road connecting cities u_i and v_i.

The next line contains integer k (0 ≤ k ≤ 10⁵) — the number of pairs of fools who visit each other.

Next k lines contain two space-separated numbers. The i-th line (i > 0) contains numbers a_i, b_i (1 ≤ a_i, b_i ≤ n). That means that the fool number 2i - 1 lives in city a_i and visits the fool number 2i, who lives in city b_i. The given pairs describe simple paths, because between every pair of cities there is only one simple path.

Output

Print n - 1 integer. The integers should be separated by spaces. The i-th number should equal the number of fools who can go on the i-th road. The roads are numbered starting from one in the order, in which they occur in the input.

Examples

Input

5
1 2
1 3
2 4
2 5
2
1 4
3 5

Output

2 1 1 1 

Input

5
3 4
4 5
1 4
2 4
3
2 3
1 3
3 5

Output

3 1 1 1 

Note

In the first sample the fool number one goes on the first and third road and the fool number 3 goes on the second, first and fourth ones.

In the second sample, the fools number 1, 3 and 5 go on the first road, the fool number 5 will go on the second road, on the third road goes the fool number 3, and on the fourth one goes fool number 1.

 题意：呃呃，就是说有n个城市，给你n-1条边，有m个人，需要从a[i]走到b[i]去，每走过一条边，这条边就加1，最后输出所有边被走过几次。

题解：每次加1？让我想到上次比赛的第二题——差分（其实这是我后来才想到的）。n个点，n-1条，可以知道这是棵树，以1为根节点，转为有根树，

两点之间走？ 想到LCA求距离的模板，但这里不是求距离，需要改一下，走的时候给走过的边权加1？邻接表存的LCA做的时候边用不上啊，怎么办，

这时候就需要用到树上差分了，从x走到y ，dis[x]+1;dis[y]+1;  dis[LCA(x,y)]-2;这是差分的思想，最后从叶节点往上跑一直到根节点，边权就等于相邻的叶子节点

怎么实现？深搜从根节点开始，回溯的时候父亲节点+=儿子节点，然后把边权赋为相邻叶子节点的值。就完成啦！还有些小细节，详见代码

var
f:array[0..300005,0..24]of longint;
a,dep,head,next,rd,dis,ans,map:array[0..500005]of longint;
e,v,i,u,n,m,j,k,x,y,root,tot:longint;
procedure add(x,y:longint);
begin
 inc(e); a[e]:=y;next[e]:=head[x];head[x]:=e; inc(rd[y]);
end;
procedure dfs(u:longint);
var i,v:longint;
  begin
  i:=head[u];
  while i>0 do
   begin
     v:=a[i];
     if dep[v]=0 then
      begin
       dep[v]:=dep[u]+1;
       f[v,0]:=u;
       dfs(v);
      end;
      i:=next[i];
   end;
 end;
 procedure rdfs(u,s:longint);
 var v,i:longint;
 begin
   i:=head[u];
   while i>0 do
    begin
      v:=a[i];
      if v<>s then//不能用dep[v]>dep[u]作为条件！这样会WA，要v不等于它的爷爷节点才行（貌似我打过的关于树的都是这样写的）
       begin
         rdfs(v,u);
       //   writeln(u,' ',v);
         dis[u]:=dis[u]+dis[v];
         ans[map[i]]:=ans[map[i]]+dis[v];
       end;
       i:=next[i];
    end;
  end;
  function lca(x,y:longint):longint;
 var k,i:longint;
  begin
    if dep[x]<dep[y] then
    begin
      k:=x;x:=y;y:=k;
    end;

    for i:=20 downto 0 do
     begin
      if dep[f[x,i]]>=dep[y] then begin x:=f[x,i];  end;
     end;
         if x=y then begin exit(x); end;
     for i:=20 downto 0 do
       if f[x,i]<>f[y,i] then
        begin
          x:=f[x,i];
          y:=f[y,i];
        end;
   exit(f[x,0]);
  end;

begin
 readln(n);
 for i:=1 to n-1 do
  begin
    inc(tot);
    readln(x,y);
    add(x,y);
    map[e]:=tot;//小技巧，建边两次，这样是为了最后输出每条边被走过几次
    add(y,x);
    map[e]:=tot;
  end;
  root:=1;dep[root]:=1;
  dfs(root);
   for i:=1 to 20 do
    for j:=1 to n do
     f[j,i]:=f[f[j,i-1],i-1];
   readln(m);
   for i:=1 to m do
    begin
     readln(x,y);
     inc(dis[x]);inc(dis[y]);
     dec(dis[lca(x,y)],2);
    end;
    rdfs(1,1);
    for i:=1 to tot do write(ans[i],' ');
end.

E - Anton and Tree

CodeForces - 734E 

Anton is growing a tree in his garden. In case you forgot, the tree is a connected acyclic undirected graph.

There are n vertices in the tree, each of them is painted black or white. Anton doesn't like multicolored trees, so he wants to change the tree such that all vertices have the same color (black or white).

To change the colors Anton can use only operations of one type. We denote it as paint(v), where v is some vertex of the tree. This operation changes the color of all vertices u such that all vertices on the shortest path from v to u have the same color (including v and u). For example, consider the tree

and apply operation paint(3) to get the following:

Anton is interested in the minimum number of operation he needs to perform in order to make the colors of all vertices equal.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of vertices in the tree.

The second line contains n integers color_i (0 ≤ color_i ≤ 1) — colors of the vertices. color_i = 0 means that the i-th vertex is initially painted white, while color_i = 1 means it's initially painted black.

Then follow n - 1 line, each of them contains a pair of integers u_i and v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i) — indices of vertices connected by the corresponding edge. It's guaranteed that all pairs (u_i, v_i) are distinct, i.e. there are no multiple edges.

Output

Print one integer — the minimum number of operations Anton has to apply in order to make all vertices of the tree black or all vertices of the tree white.

Examples

Input

11
0 0 0 1 1 0 1 0 0 1 1
1 2
1 3
2 4
2 5
5 6
5 7
3 8
3 9
3 10
9 11

Output

2

Input

4
0 0 0 0
1 2
2 3
3 4

Output

0

Note

In the first sample, the tree is the same as on the picture. If we first apply operation paint(3) and then apply paint(6), the tree will become completely black, so the answer is 2.

In the second sample, the tree is already white, so there is no need to apply any operations and the answer is 0.

题意：给你一颗树，节点被染了黑白两种颜色，但个数不确定。若一个子连通块 都为种颜色，则一次操作可以把这个连通块变为另一种颜色，现在要把树的节点

都变为一种颜色，问最少操作几次。

题解：既然一次操作能把一个连通块中节点都变色，是不是可以将他们变为一组来算更方便呢？那么第一步就是缩点了，将颜色相同的一个连通块缩为一个点，

再重新建边，得到的就是一个黑白树了（相邻节点颜色都不相同）。那操作几次怎么算？操作一次可以把一个点周围的点都变为同一种颜色，要操作的次数就是

直径/2 了，证明的话到时候再放上来。

var
t,n,m,i,j,x,y,z,e,ei,l,tot,po,v:longint;
max:int64;
c,b,head,next,a,ia,inext,ihead,xx,dis:array[-100..500005]of longint;
procedure add(x,y:longint);
begin
 inc(e); a[e]:=y; next[e]:=head[x];head[x]:=e; xx[e]:=x;
end;
procedure iadd(x,y:longint);
begin
 inc(ei); ia[ei]:=y; inext[ei]:=ihead[x];ihead[x]:=ei;
end;
procedure dfsclo(u,m:longint);
 var i,v:longint;
  begin
  i:=head[u];
  while i>0 do
   begin
     v:=a[i];
     if (c[u]=c[v])and(v<>m) then
     begin
       b[v]:=b[u];
       dfsclo(v,u);
     end;
     i:=next[i];
   end;

 end;
procedure dfs(u,m:longint);
 var i,v:longint;
 begin
  i:=ihead[u];
  while i>0 do
   begin
     v:=ia[i];
     if v<>m then
      begin
        dis[v]:=dis[u]+1;
        if dis[v]>max then
         begin
           max:=dis[v];
           po:=v;
         end;
        dfs(v,u);
       end;
      i:=inext[i];
   end;
 end;
begin
  readln(n);
 for i:=1 to n do read(c[i]);
  for i:=1 to n-1 do
   begin
     readln(x,y);
     add(x,y);
     add(y,x);
   end;
  for i:=1 to n do
   begin
    if b[i]=0 then
     begin
       inc(tot);
       b[i]:=tot;
       dfsclo(i,i);
     end;
   end;
  for i:=1 to e do
   begin
    if  b[xx[i]]<>b[a[i]] then
     begin
      iadd(b[xx[i]],b[a[i]]);
    //   iadd(b[a[i]],b[xx[i]]);
     end;
   end;
 //  for i:=1 to n do writeln(b[i], ' ');
   dfs(1,1);
   fillchar(dis,sizeof(dis),0);
   dfs(po,po);
   writeln((max+1) div 2);
end.