ECNU的oj，题很多的样子。。。orz
附上一篇讲树上差分很不错的blog
初学树上差分第一题吧算是，简单的分析一下就可以发现只需要求出来各条边在query中被覆盖到的次数就可以了。利用边的树上差分很容易就能求出来。每次求出lca之后分为两条链，则cf[u]++,cf[v]++,cf[lca]-=2；即可处理完毕。最后推的时候用dfs从下往上推就可以了。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=2e5+5;
const int mod=1e9+7;
int n;
int w[maxn];
int cf[maxn];
vector G[maxn];
int fa[maxn][20],deg[maxn];
void bfs(int root)
{
queue que;
deg[root]=0;
fa[root][0]=root;
que.push(root);
int tmp,len,v;
while(!que.empty())
{
tmp=que.front();que.pop();
for(int i=1;i<20;i++) fa[tmp][i]=fa[fa[tmp][i-1]][i-1]; len=G[tmp].size(); for(int i=0;i<len;i++) {="" v="G[tmp][i];" if(v="=fa[tmp][0])continue;" deg[v]="deg[tmp]+1;" fa[v][0]="tmp;" que.push(v);="" }="" int="" lca(int="" u,int="" v)="" if(deg[u]="">deg[v])
swap(u,v);
int hu=deg[u],hv=deg[v];
int tu=u,tv=v;
for(int det=hv-hu,i=0;det;det>>=1,i++)
if(det&1)
tv=fa[tv][i];
if(tu==tv)
return tu;
for(int i=19;i>=0;i--)
{
if(fa[tu][i]==fa[tv][i])
continue;
tu=fa[tu][i];
tv=fa[tv][i];
}
return fa[tu][0];
}</len;i++)>
void dfs(int x,int fa)
{
int len=G[x].size(),v;
for(int i=0;i<len;i++) {="" v="G[x][i];" if(v="=fa)continue;" dfs(v,x);="" cf[x]+="cf[v];" }="" int="" main()="" q,u,v,la;="" scanf("%d",&n);="" for="" (int="" i="1;i<n;i++)" scanf("%d%d%d",&u,&v,&w[i]);="" g[u].push_back(v);="" g[v].push_back(u);="" sort(w+1,w+n);="" bfs(1);="" scanf("%d",&q);="" while(q--)="" scanf("%d%d",&u,&v);="" la="lca(u,v);" cf[u]++,cf[v]++,cf[la]-="2;" dfs(1,-1);="" sort(cf+1,cf+1+n);="" ll="" ans="0;" for(int="">0&&cf[i];i--)
{
ans+=1LL*cf[i]*w[n-i+1];
}
printf("%lld\n",ans);
return 0;
}</len;i++)>