P2664 树上游戏

　　作为一道经典的点分治题目，此题能很好的考察对点分治的运用。

　　个人认为点分治的本质在于：对于树上近乎n²的路径询问，通过有效的

划分，使之能在稳定的时间内通过 存储信息——获取信息 的经典方式来求

出答案。

　　由此看出点分治的关键在于存储信息与获取信息的方式。

　　点分治的模板套上之后我们只需要考虑的是子树与子树间产生的贡献。

　　往往的套路是我们将当前子树之外子树和根的信息通过特定的方式储存，

然后再可以对于当前子树中的节点统计其到储存信息对应的节点的路径的答案

。

　　关于这一题，题目中给了每个节点种类达到 n 的级别的一个属性。因此往往使

人觉得十分棘手。抛开百分百错误的暴力做法，考虑如何利用点分治的优秀划分方

式使问题可做处理。

　　考虑点分治过程中计算一条由根出发的路径的贡献，因为属性相同只能计算一

次（关于此类统计有一种常用套路：我们使统计的方式唯一化，即我们定义一种方

式使得每一种贡献只在某一特定的情况下被统计。）对于此题我们使得每条路路径

中每种属性只在它第一次出现时被统计。

　　那么考虑如何统计使之便于其它子树中的节点查询进而统计答案。因为统计的

一般路径都是由一条由根出发的路径与一条由根的子树出发的路径合并而成。所以

统计还可能有重复，所以我们还需要抉择一下在哪统计（此时一种属性最多只有两

次被统计）。

　　因为深搜处理答案的时候当前子树的信息时常变动所以将在当前子树种出现的

属性特殊处理较为方便。

　　具体细节并不想写......

  1 #include<bits/stdc++.h>
  2 #define ll long long 
  3 using namespace std;
  4 int n,x,y,tot,root;
  5 int head[100050];
  6 int nex[200050];
  7 int ver[200050];
  8 int col[100050];
  9 int siz[100050];
 10 ll val[100050];
 11 ll ans[100050];
 12 int maxn[100050];
 13 bool vis[100050];
 14 bool vic[100050];
 15 int t[100050],top;
 16 ll sumval;
 17 void add(int x,int y)
 18 {
 19     nex[++tot]=head[x];
 20     ver[tot]=y;
 21     head[x]=tot;
 22 }
 23 void getroot(int u,int fa,int SIZ)
 24 {
 25     siz[u]=1;maxn[u]=0;
 26     for(int i=head[u];i;i=nex[i])
 27         if(ver[i]!=fa&&!vis[ver[i]])
 28         {
 29             getroot(ver[i],u,SIZ);
 30             maxn[u]=max(maxn[u],siz[ver[i]]);
 31             siz[u]+=siz[ver[i]];
 32         }
 33     maxn[u]=max(maxn[u],SIZ-siz[u]);
 34     if(maxn[u]<maxn[root])    root=u;
 35 }
 36 void calc(int u,int fa,int opt)
 37 {
 38     bool flag=false;
 39     if(!vic[col[u]])
 40     {
 41         flag=true;
 42         vic[col[u]]=true;
 43     }
 44     siz[u]=1;
 45     for(int i=head[u];i;i=nex[i])
 46         if(ver[i]!=fa&&!vis[ver[i]])
 47         {
 48             calc(ver[i],u,opt);
 49             siz[u]+=siz[ver[i]];
 50         }
 51     if(flag)
 52     {
 53         vic[col[u]]=false;
 54         if(opt==-1)
 55             t[++top]=col[u];
 56         sumval+=siz[u]*opt;
 57         val[col[u]]+=siz[u]*opt;
 58     }
 59 }
 60 void work(int u,int fa,ll SUM,int SIZOUTSIDE,int TOT)
 61 {
 62     bool flag=false; 
 63     if(!vic[col[u]])
 64     {
 65         flag=true;
 66         vic[col[u]]=true;
 67         SUM-=val[col[u]];
 68         ++TOT;
 69     }
 70     ans[u]+=(ll)TOT*SIZOUTSIDE+SUM;
 71     for(int i=head[u];i;i=nex[i])
 72         if(ver[i]!=fa&&!vis[ver[i]])
 73             work(ver[i],u,SUM,SIZOUTSIDE,TOT);
 74     if(flag)
 75         vic[col[u]]=false;
 76 }
 77 void dfs(int u)
 78 {
 79     vis[u]=true;
 80     calc(u,0,1);
 81     ans[u]+=sumval;
 82     t[++top]=col[u];
 83     for(int i=head[u];i;i=nex[i])
 84         if(!vis[ver[i]])
 85         {
 86             vic[col[u]]=true; 
 87             calc(ver[i],0,-1);
 88             vic[col[u]]=false;
 89             val[col[u]]-=siz[ver[i]];
 90             work(ver[i],0,sumval-siz[ver[i]],siz[u]-siz[ver[i]],0);
 91             vic[col[u]]=true;
 92             calc(ver[i],0,1);
 93             vic[col[u]]=false;
 94             val[col[u]]+=siz[ver[i]];
 95         }
 96     while(top)
 97     {
 98         val[t[top]]=0;
 99         --top;
100     }
101     sumval=0;
102     for(int i=head[u];i;i=nex[i])
103         if(!vis[ver[i]])
104         {
105             root=0;
106             getroot(ver[i],0,siz[ver[i]]);
107             dfs(root);
108         }
109 }
110 int main()
111 {
112     scanf("%d",&n);
113     for(int i=1;i<=n;++i)
114         scanf("%d",&col[i]);
115     for(int i=1;i<n;++i)
116     {
117         scanf("%d%d",&x,&y);
118         add(x,y);    add(y,x);
119     }maxn[0]=n+1;
120     getroot(1,0,n);    dfs(root);
121     for(int i=1;i<=n;++i)
122         printf("%lld
",ans[i]);
123     return 0;
124 }

View Code