[JLOI2014]松鼠的新家树上差分

差分

一开始竟然想分情况讨论来差分，然后发现各自情况要分析，就是为了解决中间节点重复计算的问题，结果最后一想，中间重复计算了一次，那我最后减掉不就好了么，，，那这就是一道差分裸题了（这是唯一不同的地方）

由于是树上差分，所以要先求出所有需要的LCA，然后就是树上差分的套路了

这里由于进来后再出去是只能算一次的，所以略有不同，但实际上也不麻烦，因为直接维护是很困难的，所以不如不维护这个地方，直接在统计答案的时候减掉这些多出来的。

  1 using namespace std;
  2 #define R register int
  3 #define AC 300100
  4 #define D printf("line in %d
",__LINE__);
  5 int n,cnt;//cnt是计LCA的
  6 int date[AC*2],Next[AC*2],Head[AC],tot=1;//存图
  7 int qdate[AC*2],qNext[AC*2],qHead[AC],qtot=1;//存询问
  8 int LCA[AC],ans[AC*2];//直接按顺序求，所以线性顺序即可
  9 int father[AC],t[AC],power[AC],fa[AC];
 10 bool vis[AC];
 11 //error!!!前向星因为是双向边，然后询问也是双向的，所以这些数组都要*2啊！！！
 12 inline int read()
 13 {
 14     int x=0;char c;
 15     while(isspace(c=getchar()));
 16     while(c>='0' && c<='9')x=x*10+c-'0',c=getchar();
 17     return x;
 18 }
 19 
 20 void add1(int f,int w)//加图
 21 {
 22     date[++tot]=w,Next[tot]=Head[f],Head[f]=tot;
 23     date[++tot]=f,Next[tot]=Head[w],Head[w]=tot;
 24 }
 25 
 26 int find(int x)
 27 {
 28     if(father[x]==x)    return x;
 29     else return father[x]=find(father[x]);
 30 }
 31 
 32 void add2(int f,int w)//加询问
 33 {
 34     qdate[++qtot]=w,qNext[qtot]=qHead[f],qHead[f]=qtot;
 35     qdate[++qtot]=f,qNext[qtot]=qHead[w],qHead[w]=qtot;
 36 }
 37 
 38 void DFS(int x) 
 39 {
 40     R now;
 41     vis[x]=true;
 42     for(R i=Head[x]; i ;i=Next[i])
 43     {
 44         now=date[i];
 45         if(!vis[now])
 46         {
 47             DFS(now);
 48             father[now]=x;//访问完所有的字节点后接上来
 49         }
 50         else fa[x]=now;//不然就是父亲，因为是点权，所以直接等于now就好了
 51     }
 52     for(R i=qHead[x]; i ;i=qNext[i])
 53     {
 54         now=qdate[i];
 55         if(vis[now] && !ans[i ^ 1])ans[i]=find(now);
 56     } 
 57 }
 58 
 59 void pre()
 60 {
 61     R a,b;
 62     n=read();
 63     for(R i=1;i<=n;i++)  t[i]=read();
 64     for(R i=1;i<n;i++)
 65     {
 66         a=read(),b=read();  
 67         add1(a,b);
 68     }
 69     for(R i=1;i<n;i++)//添加询问
 70         add2(t[i],t[i+1]);
 71     for(R i=1;i<=n;i++)father[i]=i;
 72     DFS(1);
 73     for(R i=1;i<=n*2+1;i++)
 74         if(ans[i])  LCA[++cnt]=ans[i];
 75 }
 76 
 77 void getans(int x)//统计答案,可以统计进入
 78 {
 79     R now;
 80     for(R i=Head[x]; i ;i=Next[i])
 81     {
 82         now=date[i];
 83         if(now!=fa[x])  
 84         {
 85             getans(now);
 86             power[x]+=power[now];
 87         }
 88     }
 89 }
 90 
 91 void work()
 92 {
 93     for(R i=1;i<n;i++)
 94     {
 95         power[t[i]]++,power[t[i+1]]++,power[LCA[i]]--,power[fa[LCA[i]]]--;//由于题目特殊性，不能每次都+1,因为进出房间只是一次
 96     }//但是这样并不好计算，那完全可以直接像平常一样统计啊，由于这样每个中间节点都会被重复计算一次，那输出的时候-1不就好了吗  
 97     getans(1);
 98     for(R i=2;i<=n;i++)//因为要按下标输出，但是重复计算的是序列中间的，所以是要序列中间都-1,所以先处理
 99         power[t[i]]--;
100     for(R i=1;i<=n;i++)  printf("%d
",power[i]);
101 }
102 
103 int main()
104 {
105     freopen("in.in","r",stdin);
106     pre();
107     work();
108     fclose(stdin);
109     return 0;
110 }

[JLOI2014]松鼠的新家 树上差分

[JLOI2014]松鼠的新家树上差分