題目描述
Farmer John has installed a new system of
pipes to transport milk between the
stalls in his barn (
), conveniently numbered
. Each pipe connects a pair of stalls, and all stalls are connected to each-other via paths of pipes.
FJ is pumping milk between
pairs of stalls (
). For the
th such pair, you are told two stalls
and
, endpoints of a path along which milk is being pumped at a unit rate. FJ is concerned that some stalls might end up overwhelmed with all the milk being pumped through them, since a stall can serve as a waypoint along many of the
paths along which milk is being pumped. Please help him determine the maximum amount of milk being pumped through any stall. If milk is being pumped along a path from
to
, then it counts as being pumped through the endpoint stalls
and
, as well as through every stall along the path between them.
FJ給他的牛棚的N(2≤N≤50,000)個隔間之間安裝了N-1根管道，隔間編号從1到N。所有隔間都被管道連通了。
FJ有K(1≤K≤100,000)條運輸牛奶的路線，第i條路線從隔間si運輸到隔間ti。一條運輸路線會給它的兩個端點處的隔間以及中間途徑的所有隔間帶來一個機關的運輸壓力，你需要計算壓力最大的隔間的壓力是多少。
輸入輸出格式
輸入格式：
The first line of the input contains
.
The next
lines each contain two integers
() describing a pipe
between stalls
describing the endpoint
stalls of a path through which milk is being pumped.
輸出格式：
An integer specifying the maximum amount of milk pumped through any stall in the
barn.
輸入輸出樣例
輸入樣例#1：
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4 輸出樣例#1：
9 解題思路
感謝洛谷裡@j_william 指出我的錯誤，改正了重發一個。
我之前并沒有聽說過樹上差分這麼進階的東東，于是為了練手速花了40min敲了一個樹剖套線段樹(蒟蒻碼力不足)，寫好了線段樹的一堆函數定義（maketree() pushdown() query() update()），剩着函數内部等待填充，感覺到一種絕望：還有那麼多，要敲到啥時候啊。。。正在調整心态準備敲線段樹時，突然想到，這題好像隻是區間修改、單點查詢？差分的樹狀數組！
于是内心一片愉悅啊，愉快地敲完短得多的樹狀數組，順利1A！
正經的題解
增加一條x到y的路徑，就是把x到y的所有點的點權加1，很容易想到這是樹剖闆題的第一個操作,又由于這題隻用單點查詢，于是再套單點修改、區間查詢的樹狀數組即可
源代碼
#include<bits/stdc++.h>
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
#define lowbit(x) (x)&(-(x))
using namespace std;
int n,k;
struct Edge{
int next,to;
}e[100010];
int cnt=1,head[50010];
void add_e(int u,int v)
{
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt++;
}
struct tree{
int fa;
vector<int> son;
int dep;
int num_to;
int wson;
int top;
int new_id;
}t[50010];
bool vis[50010];
int dfs1(int u,int fa,int depth)
{
vis[u]=1;
t[u].fa=fa;
t[u].dep=depth;
t[u].num_to=1;
for(int i=head[u],weightest=-1,w;i;i=e[i].next)
{
int v=e[i].to;
if(vis[v]) continue;
t[u].son.push_back(v);
w=dfs1(v,u,depth+1);
if(w>weightest)
{
t[u].wson=v;
weightest=w;
}
t[u].num_to+=w;
}
return t[u].num_to;
}
int num_id=1;
void dfs2(int u,int top)
{
t[u].top=top;
t[u].new_id=num_id++;
int sz=t[u].son.size();
if(sz==0)
return;
dfs2(t[u].wson,top);
for(int i=0;i<sz;i++)
{
int v=t[u].son[i];
if(v==t[u].wson) continue;
dfs2(v,v);
}
}
int s[50010]={0};
void add(int node,int w)
{
while(node<=n)//就是這裡錯了，我原來的題解沒寫'='，資料水沒被卡，，，
{
s[node]+=w;
node+=lowbit(node);
}
}
int ask(int node)
{
int ans=0;
while(node)
{
ans+=s[node];
node-=lowbit(node);
}
return ans;
}
void up(int x,int y)//////////////////////////////////////
{
while(t[x].top!=t[y].top)//x向y上靠 即y.top 更高
{
if(t[t[x].top].dep<t[t[y].top].dep) swap(x,y);
add(t[x].new_id-1,-1);
add(t[t[x].top].new_id,1);
x=t[t[x].top].fa;
}
if(t[x].new_id>t[y].new_id) swap(x,y);
add(t[x].new_id,1);
add(t[y].new_id+1,-1);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add_e(x,y);
add_e(y,x);
}
dfs1(1,1,1);
dfs2(1,1);
for(int i=0,x,y;i<k;i++)
{
scanf("%d%d",&x,&y);
up(x,y);
}
int maxn=s[1];
for(int i=2;i<=n+1;i++)//還有這裡，我不知道當時咋想的，寫了個i<=50001
{
maxn=max(maxn,ask(i));
}
printf("%d",maxn);
return 0;
}