洛谷P3258 [JLOI2014]松鼠的新家【LCA+树上差分】
简要题意
树上n个节点，给定路径，求每个点经过次数
题意分析
对于每两个点，有两种情况，第一种，他们的lca为本身，第二种，他们有公共祖先，又要求他们的点经过次数，暴力是不可能的，复杂度不对，所以可以想到树上差分再求前缀和，在差分的过程中自然也要求lca了。
还有要注意的就是对于开始的起点和结束的终点是要特判经过的，其他的起点不计入次数。
树上差分
树上差分主要用于求解一些树上的路径问题
它通过利用树的一些性质，用一个差分数组来实现对一条路径的操作，这涉及到路径的 起，终点 与lca。
一般情况下：一个点的真实权值为其所在子树内所有点的差分数组的值的和
树上差分一般不适用于询问和操作嵌套的题目，这时一般用树链剖分解决
LCA
倍增Tarjan树剖，自行百度
关于代码：
#include<bits/stdc++.h>
#define re register
#define ll long long
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
using namespace std;
inline int read()
{
int k=1,sum=0;
char c=getchar();
for(;c<'0' || c>'9';c=getchar()) if(c=='-') k=-1;
for(;c>='0' && c<='9';c=getchar()) sum=sum*10+c-'0';
return sum*k;
}
const int N=3e5+10;
struct Edge
{
int to,nxt;
}edge[N*2];
int head[N],cnt;
inline void Add(int x,int y)
{
edge[++cnt].to=y;edge[cnt].nxt=head[x];head[x]=cnt;
}
int n;
int a[N];
queue<int> Q;
int dep[N];
int t;
int f[N][26];
int cf[N];
inline void bfs()
{
Q.push(1);
dep[1]=1;
while(!Q.empty())
{
int x=Q.front();Q.pop();
for(re int i=head[x];i;i=edge[i].nxt)
{
int y=edge[i].to;
if(dep[y]) continue;
dep[y]=dep[x]+1;
f[y][0]=x;
for(re int j=1;j<=t;++j) f[y][j]=f[f[y][j-1]][j-1];
Q.push(y);
}
}
}
inline int LCA(int x,int y)
{
if(dep[x]>dep[y]) swap(x,y);
for(re int i=t;i>=0;--i) if(dep[f[y][i]]>=dep[x]) y=f[y][i];
if(x==y) return x;
for(re int i=t;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
bool vis[N];
inline void dfs(int x)
{
vis[x]=1;
for(re int i=head[x];i;i=edge[i].nxt)
{
int y=edge[i].to;
if(vis[y]) continue;
dfs(y);
cf[x]+=cf[y];
}
}
int main()
{
n=read();t=(log(n)/log(2))+1;
for(re int i=1;i<=n;++i) a[i]=read();
for(re int i=1;i<n;++i)
{
int x=read(),y=read();
Add(x,y);Add(y,x);
}
bfs();
for(re int i=1;i<n;++i)
{
int start=a[i],to=a[i+1],lca=LCA(start,to);
if(i==1)
{
if(lca==start) {++cf[to];--cf[f[start][0]];continue;}
if(lca==to) {++cf[start];--cf[f[to][0]];continue;}
++cf[start];++cf[to];--cf[lca];--cf[f[lca][0]];continue;
}
if(i==n-1)
{
if(lca==start) {++cf[f[to][0]];--cf[start];continue;}
if(lca==to) {++cf[f[start][0]];--cf[to];continue;}
++cf[f[start][0]];++cf[f[to][0]];--cf[lca];--cf[f[lca][0]];continue;
}
if(lca==start) {++cf[to];--cf[start];continue;}
if(lca==to) {++cf[f[start][0]];--cf[f[to][0]];continue;}
++cf[f[start][0]];++cf[to];--cf[lca];--cf[f[lca][0]];
}
dfs(1);
for(re int i=1;i<=n;++i) cout<<cf[i]<<endl;
return 0;
} 1、andorid里的手势电话学习（下）
2、其他
3、我比较挫.现在才发现GridView 可以像DataList 一样使用自定义模板
4、数模 11多元回归分析
5、Restful设计规范，前后端分离的优缺点对比