树上差分 (瞎bb) [树上差分][LCA]

做noip2015的运输计划写了好久好久写不出来 QwQ

于是先来瞎bb一下树上差分混积分

树上差分有2个常用的功能：

(1)记录从点i到i的父亲这条路径走过几次

(2)将每条路径(s,t)上的每个点权值增加1，求各点权值

首先我们建立权值数组sum[]

　　对于(1)，对于每一条路径(s,t)，操作: sum[s]++; sum[t]++; sum[lca(s,t)]-=2;

　　　　　　再利用dfs将子节点的sum值加入到父亲节点中即可

　　　　　　 sum[i]的数值就表示从点i到i的父亲这条路径走过几次

　　对于(2)，对于每一条路径(s,t)，操作：sum[s]++; sum[t]++; sum[lca(s,t)]--; sum[father[lca(s,t]]--;

　　　　　　再利用dfs将子节点的sum值加入到父亲节点中即可

　　　　　　 sum[i]表示每一点的权值

贴上(1)的代码

ps1:利用tarjan算法求出lca(s,t)

ps2:无向边变单向边增加效率真的吗→_→

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<vector>
  5 using namespace std;
  6 
  7 //来点有理有据的底层优化吧！ 
  8 inline int read(){
  9     int re=0;
 10     char ch;
 11     bool flag=0;
 12     while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
 13     ch=='-'?flag=1:re=ch-'0';
 14     while((ch=getchar())>='0'&&ch<='9')  re=(re<<1)+(re<<3)+ch-'0';
 15     return flag?-re:re;
 16 }
 17 
 18 struct edge{
 19     int to,next;
 20     edge(int to=0,int next=0):
 21         to(to),next(next){}
 22 };
 23 
 24 struct ask{
 25     int from,to,lca;
 26     ask(int from=0,int to=0,int lca=0):
 27         from(from),to(to),lca(lca){}
 28 };
 29 
 30 typedef pair<int,int> PII;
 31 
 32 const int maxn=300001;
 33 
 34 vector<edge> edges;
 35 vector<edge> ques;
 36 vector<edge> tree;
 37 vector<ask> qu;
 38 int head[maxn],had[maxn];
 39 int tmp_head[maxn];
 40 int F[maxn],son[maxn];
 41 int sum[maxn];
 42 int n,q,root;
 43 int cnt;
 44 int par[maxn];
 45 bool vis[maxn];
 46 
 47 inline void add_edge(int from,int to){
 48     edges.push_back(edge(to,head[from]));
 49     head[from]=++cnt;
 50     edges.push_back(edge(from,head[to]));
 51     head[to]=++cnt;
 52 }
 53 
 54 inline void add_ques(int from,int to){
 55     ques.push_back(edge(to,had[from]));
 56     had[from]=++cnt;
 57     ques.push_back(edge(from,had[to]));
 58     had[to]=++cnt;
 59 }
 60 
 61 //把双向边转为单向边
 62 //ps  一般不用对吧
 63 inline void add_branch(int from,int to){
 64     tree.push_back(edge(to,tmp_head[from]));
 65     tmp_head[from]=++cnt;
 66 }
 67 
 68 void make_tree(int x,int fa){
 69     for(int ee=head[x];ee;ee=edges[ee].next)
 70         if(edges[ee].to!=fa){
 71             add_branch(x,edges[ee].to);
 72             make_tree(edges[ee].to,x);
 73         }
 74 }
 75 
 76 void init(){
 77     n=read(),q=read(),root=read();
 78     cnt=0;
 79     edges.push_back(edge(0,0));
 80     for(int i=1;i<n;i++){
 81         int from=read(),to=read();
 82         add_edge(from,to);
 83     }
 84     cnt=0;
 85     ques.push_back(edge(0,0));
 86     for(int i=0;i<q;i++){
 87         int from=read(),to=read();
 88         qu.push_back(ask(from,to,0));
 89         add_ques(from,to);
 90     }
 91     cnt=0;
 92     tree.push_back(edge(0,0));
 93     make_tree(root,0);
 94     swap(head,tmp_head);
 95 }
 96 
 97 int find(int x){
 98     return par[x]==x?x:par[x]=find(par[x]);
 99 }
100 
101 //求lca 
102 void tarjan(int x){
103     for(int ee=head[x];ee;ee=tree[ee].next){
104         tarjan(tree[ee].to);
105         par[tree[ee].to]=x;
106         vis[tree[ee].to]=1;
107     }
108     for(int ee=had[x];ee;ee=ques[ee].next)
109         if(vis[ques[ee].to])
110             qu[(ee-1)>>1].lca=find(ques[ee].to);
111 }
112 
113 void dfs_sum(int x){
114     for(int ee=head[x];ee;ee=tree[ee].next){
115         dfs_sum(tree[ee].to);
116         sum[x]+=sum[tree[ee].to];
117     }
118 }
119 
120 void solve(){
121     for(int i=1;i<=n;i++)  par[i]=i;
122     tarjan(root);
123     
124     for(int i=0;i<q;i++){
125         ask qq=qu[i];
126         sum[qq.from]++;
127         sum[qq.to]++;
128         sum[qq.lca]-=2;
129     }
130     dfs_sum(root);
131     
132     for(int i=1;i<=n;i++)
133         printf("%d  ",sum[i]);
134 }
135 
136 int main(){
137     //freopen("temp.in","r",stdin);
138     init();
139     solve();
140     return 0;
141 }