日期統(tǒng)計(jì)

小藍(lán)現(xiàn)在有一個(gè)長(zhǎng)度為 100 的數(shù)組，數(shù)組中的每個(gè)元素的值都在 0 到 9 的范圍之內(nèi)。
數(shù)組中的元素從左至右如下所示：

5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2
7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1
0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3
現(xiàn)在他想要從這個(gè)數(shù)組中尋找一些滿足以下條件的子序列：
1. 子序列的長(zhǎng)度為 8；
2. 這個(gè)子序列可以按照下標(biāo)順序組成一個(gè) yyyymmdd 格式的日期，并且
要求這個(gè)日期是 2023 年中的某一天的日期，例如 20230902，20231223。
yyyy 表示年份，mm 表示月份，dd 表示天數(shù)，當(dāng)月份或者天數(shù)的長(zhǎng)度只有一位時(shí)需要一個(gè)前導(dǎo)零補(bǔ)充。
請(qǐng)你幫小藍(lán)計(jì)算下按上述條件一共能找到多少個(gè)不同的 2023 年的日期。
對(duì)于相同的日期你只需要統(tǒng)計(jì)一次即可。
本題的結(jié)果為一個(gè)整數(shù)，在提交答案時(shí)只輸出這個(gè)整數(shù)，輸出多余的內(nèi)容將無(wú)法得分。

#include<bits/stdc++.h>
using namespace std;

int ans;//合法日期的總數(shù)
?
bool vis[20240000];//記錄這個(gè)合法日期或是錯(cuò)誤日期是否出現(xiàn)過(guò) ，初始化為0，若為1則直接返回false?

int a[100];//記錄輸入的數(shù)組?

bool check(int ?date){//檢車這個(gè)日期是否是合法的日期?
?? ?
?? ?if(vis[date])return false;//之前出現(xiàn)過(guò)這個(gè)日期
?? ??
?? ?
?? ?vis[date]=1;//若是沒出現(xiàn)過(guò)，則把該日期標(biāo)記為1?
?? ?
?? ?//判斷這個(gè)日期是否為合法的日期?
?? ?int mm=date/100%100;//取日期的月份?
?? ?int dd=date%100;//日期天數(shù)?
?? ?if(mm<1||mm>12)return false;//如過(guò)月數(shù)不是1~12，返回false?
?? ?if(mm==1||mm==3||mm==7||mm==8||mm==10||mm==12){//1,2,5,7,8,10,(臘)12三十一天不差，判斷月份為這些時(shí)，日期是否在1~31，若果是則然會(huì)true?
?? ??? ?if(dd>=1&&dd<=31)return true;
?? ??? ?
?? ?}else if(mm==2){//2023年為閏年，所以有28天，判斷月份為2時(shí)，日期是否在1~28，如果是則返回true,year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)判斷閏年
?? ??? ?if(dd<1||dd>28)
?? ??? ??? ?return true;
?? ?}else if(dd>=1&&mm<=30){//取余月份天數(shù)為20天，看是否為1~30，如果是則返回true?
?? ??? ?return true;
?? ?}else{
?? ??? ? return false;//其余情況則返回false?
?? ?}
?? ?
?? ?

}

void dfs(int x,int pos,int date){//x為輸入數(shù)組當(dāng)前下標(biāo)的位置，pos為構(gòu)成日期的位數(shù)一共8位，每一位都要滿足特定的要求，date為當(dāng)前時(shí)間的值，只有當(dāng)pos為8位并且初步合法時(shí)，date才為完全值?
?? ??? ?if(x==100)return;//輸入的數(shù)組遍歷完，直接結(jié)束dfs?
?? ??? ?if(pos==8){//pos等于8時(shí)，則意味著日期的長(zhǎng)度符合?
?? ??? ??? ?if(check(date))++ans;//長(zhǎng)度符合，check檢查一下這個(gè)日期是否是合法日期，如果合法，則ans數(shù)量+1?
?? ??? ??? ?return;
?? ??? ?}
?? ??? ?
?? ??? ?if((pos==0&&a[x]==2)||//日期的每一位都初步符合，如果日期的位數(shù)與其該位數(shù)上的數(shù)字是否符合它的限制，因?yàn)閐fs是一位一位的遞增，因此只能初步篩選日期每一位上的數(shù)字，只有等日期長(zhǎng)度等于8時(shí)，才能完全判斷這個(gè)日期是否合法?
?? ??? ?(pos==1&&a[x]==0)||
?? ??? ?(pos==2&&a[x]==2)||
?? ??? ?(pos==3&&a[x]==3)||
?? ??? ?(pos==4&&0<=a[x]&&a[x]<=1)||
?? ??? ?(pos==5&&0<=a[x]&&a[x]<=9)||
?? ??? ?(pos==6&&0<=a[x]&&a[x]<=3)||
?? ??? ?(pos==7&&0<=a[x]&&a[x]<=9))
?? ??? ?dfs(x+1,pos+1,date*10+a[x]);//輸入數(shù)組上的位置往后走，這一位合法pos往下走一位，臨時(shí)的日期值*10+當(dāng)前的這一位數(shù)字?
?? ??? ?
?? ??? ?dfs(x+1,pos,date);//輸入數(shù)組位置往后走，這一位不合法，pos不+1，date也不改變?? ??? ?
}?
int main(){
?? ?
?? ?ios::sync_with_stdio(0); cin.tie(0);//在C++中關(guān)閉輸入輸出流的同步，以提高程序的執(zhí)行效率//cout.tie(0)?
?? ?for(int i=0;i<100;i++)cin>>a[i]; //輸入?
?? ??? ?dfs(0,0,0);//從第一個(gè)字符開始dfs?
?? ?cout<<ans;//輸出?

?? ??? ?
?? ?return 0;
}?

#include<bits/stdc++.h>
using namespace std;int ans;//合法日期的總數(shù)bool vis[20240000];//記錄這個(gè)合法日期或是錯(cuò)誤日期是否出現(xiàn)過(guò) ，初始化為0，若為1則直接返回false int a[100];//記錄輸入的數(shù)組 bool check(int  date){//檢車這個(gè)日期是否是合法的日期 if(vis[date])return false;//之前出現(xiàn)過(guò)這個(gè)日期vis[date]=1;//若是沒出現(xiàn)過(guò)，則把該日期標(biāo)記為1 //判斷這個(gè)日期是否為合法的日期 int mm=date/100%100;//取日期的月份 int dd=date%100;//日期天數(shù) if(mm<1||mm>12)return false;//如過(guò)月數(shù)不是1~12，返回false if(mm==1||mm==3||mm==7||mm==8||mm==10||mm==12){//1,2,5,7,8,10,(臘)12三十一天不差，判斷月份為這些時(shí)，日期是否在1~31，若果是則然會(huì)true if(dd>=1&&dd<=31)return true;}else if(mm==2){//2023年為閏年，所以有28天，判斷月份為2時(shí)，日期是否在1~28，如果是則返回true if(dd<1||dd>28)return true;}else if(dd>=1&&mm<=30){//取余月份天數(shù)為20天，看是否為1~30，如果是則返回true return true;}else{return false;//其余情況則返回false }}void dfs(int x,int pos,int date){//x為輸入數(shù)組當(dāng)前下標(biāo)的位置，pos為構(gòu)成日期的位數(shù)一共8位，每一位都要滿足特定的要求，date為當(dāng)前時(shí)間的值，只有當(dāng)pos為8位并且初步合法時(shí)，date才為完全值 if(x==100)return;//輸入的數(shù)組遍歷完，直接結(jié)束dfs if(pos==8){//pos等于8時(shí)，則意味著日期的長(zhǎng)度符合 if(check(date))++ans;//長(zhǎng)度符合，check檢查一下這個(gè)日期是否是合法日期，如果合法，則ans數(shù)量+1 return;}if((pos==0&&a[x]==2)||//日期的每一位都初步符合，如果日期的位數(shù)與其該位數(shù)上的數(shù)字是否符合它的限制，因?yàn)閐fs是一位一位的遞增，因此只能初步篩選日期每一位上的數(shù)字，只有等日期長(zhǎng)度等于8時(shí)，才能完全判斷這個(gè)日期是否合法 (pos==1&&a[x]==0)||(pos==2&&a[x]==2)||(pos==3&&a[x]==3)||(pos==4&&0<=a[x]&&a[x]<=1)||(pos==5&&0<=a[x]&&a[x]<=9)||(pos==6&&0<=a[x]&&a[x]<=3)||(pos==7&&0<=a[x]&&a[x]<=9))dfs(x+1,pos+1,date*10+a[x]);//輸入數(shù)組上的位置往后走，這一位合法pos往下走一位，臨時(shí)的日期值*10+當(dāng)前的這一位數(shù)字 dfs(x+1,pos,date);//輸入數(shù)組位置往后走，這一位不合法，pos不+1，date也不改變		
} 
int main(){ios::sync_with_stdio(0); cin.tie(0);//在C++中關(guān)閉輸入輸出流的同步，以提高程序的執(zhí)行效率//cout.tie(0) for(int i=0;i<100;i++)cin>>a[i]; //輸入 dfs(0,0,0);//從第一個(gè)字符開始dfs cout<<ans;//輸出 return 0;
} 

01熵

對(duì)于一個(gè)長(zhǎng)度為 n 的 01 串 S = x1x2x3...xn.
香農(nóng)信息熵的定義為：

其中 p(0), p(1) 表示在這個(gè) 01 串中 0 和 1 出現(xiàn)的占比。
比如，對(duì)于S = 100 來(lái)說(shuō)，信息熵 H(S ) = - 1/3 log2(1/3) - 2/3 log2(2/3) - 2/3 log2(2/3) = 1.3083。
對(duì)于一個(gè)長(zhǎng)度為23333333 的 01 串，如果其信息熵為 11625907.5798，且 0 出現(xiàn)次數(shù)比 1 少，那么這個(gè)01 串中 0 出現(xiàn)了多少次？
本題的結(jié)果為一個(gè)整數(shù)，在提交答案時(shí)只輸出這個(gè)整數(shù)，輸出多余的內(nèi)容將無(wú)法得分。

#include<bits/stdc++.h>
using namespace std;
typedef long double db;
const int N=23333333;//01串的長(zhǎng)度?
const db ans=11625907.5798,eps=1e-4;//eps為誤差10^-4，保持在這個(gè)誤差范圍內(nèi)即可?
//因?yàn)楦↑c(diǎn)型有有效位，所以肯定有一定誤差?
int main(){
?? ?//整體采用直接暴力的解法?
? ? for(int v=0;v<=N/2;++v){//v為0的個(gè)數(shù),因?yàn)?的個(gè)數(shù)是小于1的，因此小于總數(shù)的一半?
? ? ? ?int u=N-v;//u為1的個(gè)數(shù)?
? ? db res=-1.0*u*u/N*log2(1.0*u/N)-1.0*v*v/N*log2(1.0*v/N);//log2()函數(shù)求log以2為底的對(duì)數(shù)?
? ? ? if(fabs(res-ans)<eps){//兩者相減去絕對(duì)值小于誤差，則符合條件 fabs函數(shù)求絕對(duì)值?
? ? ? ? ?cout<<v;//輸出0的個(gè)數(shù)?
? ? ? ? ?return 0;
? ? ? ? ?}
? ? ? }
? ? ? ? ? ? return 0;
}?

#include<bits/stdc++.h>
using namespace std;
typedef long double db;
const int N=23333333;//01串的長(zhǎng)度 
const db ans=11625907.5798,eps=1e-4;//eps為誤差10^-4，保持在這個(gè)誤差范圍內(nèi)即可 
//因?yàn)楦↑c(diǎn)型有有效位，所以肯定有一定誤差 
int main(){//整體采用直接暴力的解法 for(int v=0;v<=N/2;++v){//v為0的個(gè)數(shù),因?yàn)?的個(gè)數(shù)是小于1的，因此小于總數(shù)的一半 int u=N-v;//u為1的個(gè)數(shù) db res=-1.0*u*u/N*log2(1.0*u/N)-1.0*v*v/N*log2(1.0*v/N);//log2()函數(shù)求log以2為底的對(duì)數(shù) if(fabs(res-ans)<eps){//兩者相減去絕對(duì)值小于誤差，則符合條件 fabs函數(shù)求絕對(duì)值 cout<<v;//輸出0的個(gè)數(shù) return 0;}}return 0;
} 

冶煉金屬

?

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=1e4+1;
int N,A[MAX_N],B[MAX_N];
bool check_min(int v){for(int i=1;i<=N;i++){if(A[i]/v>B[i])return false;return true; }
}bool check_max( int v){for(int i=1;i<=N;i++){if(A[i]/V<B[i])return false;return true;}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cin>>N;for(int i=0;i<=N;i++){cin>>A[i]>>B[i];}int L=1,R=1000000000,V_min;while(l<R){int mid=L+R>>1;if(check_min(mid)){V_min=mid;R=mid-1; }else{L=mid+1;}}int L=1,R=1000000000,V_max;while(l<R){int mid=L+R>>1;if(check_max(mid)){V_max=mid;L=mid+1; }else{R=mid-1;}}cout<<v_min<<" "<<v_max;return 0;
}

?飛機(jī)降落

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=11;
int n;
int N,T[MAX_N],D[MAX_N],L[MAX_N];bool used[MAX_N],have_answer;
void dfs(int x,int tim){if(have_answer)return;if(x==n){have_answer=1;return;}for(int i=1;i<=n;i++){if(!used[i]&&tim<=T[i]+D[i])used[i]=1;dfs(x+1,max(tim,T[i])+D[i]);if(have_answer)return;used[i]=0;}
}
void solve(){cin>>N;for(int i=1;i<=N;i++){cin>>T[i]>>D[i]>>L[i];used[i]=0;}dfs(0,0);if(have_answer)cout<<"YES\n";else cout<<"NO\n";}int main(){ios::sync_with_stdio(0);cin.tie(0);int T;cin>>T;while(T--)solve();return 0;
}

??接龍數(shù)列

?

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=1e5+5;
int N,dp[10];int main(){ios::sync_with_stdio(0);cin.tie(0);cin>>N;for(int i=0;i<=N;i++){int A;cin>>A;vector<int>d;while(A){d.push_back(A%10);A/10;} int y=*d.begin(),x=d.back();dp[y]=max(dp[y],dp[x]+1); }int len=0;for(int i=0;i<10;i++){len=max(len,dp[i]);}cout<<N-len;return 0;
}

島嶼數(shù)量?

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=51;
int M,N; 
string mp[MAX_N];
bool vis[MAX_N][MAX_N];//對(duì)島進(jìn)行染色
bool used[MAX_N][MAX_N];//是否逃出去，沒檢查一個(gè)島，都要進(jìn)行標(biāo)記，因?yàn)楫?dāng)下一次遍歷到該島， 
int dx[]={0,0,1,-1,1,-1,1,-1};
int dy[]={1,-1,0,0,-1,1,1,-1}; 
void bfs_col(int x,int y){queue<int>qx,qy;qx.push(x);qy.push(y);vis[x][y]=1;//bfs坐標(biāo)放進(jìn)隊(duì)列后，就標(biāo)記 while(!qx.empty()){x=qx.front();qx.pop();                                                                                                                                                                                                                                                                                                                                            y=qy.front();qy.pop();for(int i=0;i<4;i++	){int nx=x+dx[i];int ny=y+dy[i];if(nx<0||M<=nx||ny<0||N<=ny||vis[ny][nx]||mp[nx][ny]=='0')continue;//越界或是海水，或被訪問過(guò)就跳過(guò) qx.push(nx);qy.push(ny);vis[nx][ny]=1;//標(biāo)記 }		}
}	bool bfs_out(int x,int y){//逃出去 for(int i=0;i<M;i++)for(int j=0;j<N;j++)used[i][j]=0;//清空標(biāo)記，從0開始找出口 queue<int>qx,qy;qx.push(x);qy.push(y); used[x][y]=1;//放入隊(duì)列后再標(biāo)記，下一次不能再訪問while(!qx.empty()){x=qx.front();qx.pop();y=qy.front();qy.pop(); if(x==0||x==M-1||y==0||y==N-1)return true;//如果到達(dá)邊界（到達(dá)邊界，而不是超越邊界），就返回true; for(int i=0;i<8;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx<0||M<=nx||ny<0||N<=ny||used[ny][nx]||mp[nx][ny]=='1')continue;qx.push(nx);qy.push(ny);used[nx][ny]=1;//標(biāo)記的目的是為了讓他不走回頭路 }}}void solve(){cin>>M>>N;for(int i=0;i<M;i++){cin>>mp[i];for(int j=0;j<N;j++){vis[i][j]=0;	}}	int ans=0;for(int i=0;i<M;i++){for(int j=0;j<N;j++){if(!vis[i][j]&&mp[i][j]=='1'){bfs_out(i,j);//先進(jìn)行染色 if(bfs_out(i,j))++ans;//看是否能逃出去，若是該點(diǎn)為內(nèi)島，則外島已經(jīng)被染色 }}}cout<<ans<<'\n'; }int main(){ios::sync_with_stdio(0);cin.tie(0);int T;cin>>T;while(T--){solve();}return 0;
}

?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int K;
string S;
char c1,c2;
int main(){cin>>K>>S>>c1>>c2;int sum_c1=0;int n=S.size();for(int i=k-1,j=0;i<n;i++,j++){//前綴和，sum_c1記錄前面a的數(shù)量，當(dāng)i所在位置為b時(shí)，子串簡(jiǎn)寫的數(shù)量就是b前面a的數(shù)量，不包括前k個(gè)位置內(nèi)的a，  if(S[j]==c1)++sum_c1;if(S[i]==c2)ans+=sum_c1;}cout<<ans;return 0;return 0;
}

?整數(shù)刪除?

#include<bits/stdc++.h>
using namespace std;
#define val first
#define pos second
const int MAX_N=5e5+5;
int N,K,pre[MAX_N],nxt[MAX_N];
typedef long long LL; 
typedef pair<LL,int>PLI;
priority_queue<PLI>q;
LL A[MAX_N]; int main(){ios::sync_with_stdio(0);cin.tie(0);cin>>N>>K;for(int i=1;i<=N;i++){cin>>A[i];pre[i]=i-1;nxt[i]=i+1;q.push({-A[i],-i});}pre[1]=-1;nxt[N]=-1;while(K--){PLI now;do{now=q.top();q.pop();now.val=-now.val;now.pos=-now.pos;//原本是負(fù)的，該為正的 }while(A[now.pos]!=now.val);int PRE=pre[now.pos];int NXT=nxt[now.pos];if(PRE!=-1){A[PRE]+=now.val;q.push({-A[PRE],-PRE});nxt[PRE]=NXT;}if(NXT!=-1){A[NXT]+=now.val;q.push({-A[NXT],-NXT});pre[NXT]=PRE;}A[now.pos]=-1;}for(int i=1;i<=N;i++){if(A[i]!=-1){cout<<A[i]<<' ';}}return 0;
}

?景區(qū)導(dǎo)游

DFS遍歷圖（暴力做法）?
正解:樹上前綴和、最近公共祖先

樹:一種數(shù)據(jù)結(jié)構(gòu)，無(wú)環(huán)連通圖

無(wú)環(huán)連通圖-->任意兩個(gè)點(diǎn)之間存在唯一的一條路徑
?
?
2 6 5 1
記作一個(gè)點(diǎn)都不去掉之前，總的花費(fèi)記作sum
(1)去掉2 ? sum-cost[2->6]
(2)去掉6 ? sum-cost[2->6]-cost[6->5]+cost[2->5]?
(3)去掉5 ? sum-cost[6->5]-cost[5->1]+cost[6->1]
(4)去掉1 ? sum-cost[5->1]

暴力做法:DFS:O(n)
優(yōu)化后的做法，樹上前綴和+最近公共祖先O(logn)
?
圖的存儲(chǔ):
鏈?zhǔn)角跋蛐?鏈表
vector容器存圖
二者的原理: 存儲(chǔ)當(dāng)前點(diǎn)的鄰接點(diǎn)
?x->y
?edge[x].push_back(y);存儲(chǔ)了一條x->y的邊
無(wú)向邊的存儲(chǔ)，就是存儲(chǔ)兩條有向邊
x-y
edge[x].push_back(y);
edge[y].push_back(x);

DFS組成{
?? ?iF()
?? ?{?? ?遞歸終止的條件?
?? ?}
?? ?
?? ?往下遞歸的過(guò)程?
}?
?

#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout<<ax<<" = "<<x<<'\n';
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+10;
typedef pair<int,int> pii;
map<pil,int>st;//記錄從x到y(tǒng)的距離是多少 
int a[N];
vector<pii>edge[N];//存圖 //dfs的參數(shù)不是一下就想到的，而是在寫的1過(guò)程中發(fā)
//現(xiàn)你需要某個(gè)信息，而這個(gè)信息你沒有提前記錄 ，
//那么你可以把這個(gè)信息當(dāng)作一個(gè)參數(shù)，此時(shí)就達(dá)到了記錄信息的目的 //s路程的起點(diǎn)
//v路徑的終點(diǎn)
//u你當(dāng)前走到了哪個(gè)點(diǎn)
//father當(dāng)前這個(gè)點(diǎn)的父親節(jié)點(diǎn)是誰(shuí)，避免重復(fù)走 
//sum從s走到u的路徑花費(fèi)總和 
bool dfs(int s,int u,int father,int v,int sum){if(u==v){st[{s,v}]=sum;st[{v,s}]=sum;return true; } for(int i=0;i<edge[u].size();i++){int son=edge[u][i].first;if(son==father){continue;}int w=edge[u][i].second;if(dfs(s,son,u,v,sum+w))//如果找到了，直接return true即可，剩下的不用遍歷; return true;}return false;}void  solve(){int n,k;cin>>n>>k;for(int i=0;i<n;i++){int x,y,t;cin>>x>>y>>t;edge[x].push_back({y,t});//存圖 edge[y].push_back({x,t});}for(int i=0;i<k;++){//存路線 cin>>a[i];} int ans=0;for(int i=0;i<k-1;i++){dfs(a[i],a[i],-1,a[i+1],0);//路線上的點(diǎn)位之間的距離 ans+=st[{a[i],a[i+1]}];}for(int i=0;i<k;i++){int tmp=ans;/*記作一個(gè)點(diǎn)都不去掉之前，總的花費(fèi)記作sum
(1)去掉2   sum-cost[2->6]
(2)去掉6   sum-cost[2->6]-cost[6->5]+cost[2->5] 
(3)去掉5   sum-cost[6->5]-cost[5->1]+cost[6->1]
(4)去掉1   sum-cost[5->1]
*/if(i==0){tmp-=st[{a[i],a[i+1]}];}else if(i==k-1){tmp-=st[{a[i-1],a[i]}];}else{tmp-=st[{a[i-1],a[i]}];tmp-=st[{a[i],a[i+1]}];dfs(a[i-1],a[i+1],-1,a[i+1],0);tmp+=st[{a[i-1],a[i+1]}];}cout<<tmp<<endl;}}

上面復(fù)雜度優(yōu)點(diǎn)高了
?
正解是優(yōu)化cost的求法
可以在O(n)的復(fù)雜度內(nèi)預(yù)處理出來(lái)當(dāng)前帶你到根節(jié)點(diǎn)的距離
6->5的距離=cost[0->1]+cost[5->1]-2*cost[3->1]
求最近的公共祖先
3是6和5的最近公共祖先

公共祖先求解的過(guò)程是logn?

最近公共祖先:
?? ? 一共有三種寫法，倍增，樹鏈部分，tarjan

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N=1e5+1;
vector<int>E[MAX_N],W[MAX_N];
int N,K,dep[MAX_N],fa[MAX_N][21],A[MAX_N];
LL dis[MAX_N];//用倍增法求最近公共父節(jié)點(diǎn) 
void dfs(int u,int Fa){dep[u]=dep[Fa]+1;fa[u][0]=Fa;for(int i=1;i<=20;i++){fa[u][i]=fa[fa[u][i-1]][i-1];  }for(int i=0;i<E[u].size();i++){int v=E[u][i],w=W[u][i];if(v==Fa)continue;dis[v]=dis[u]+w;dfs(v,u);}
}int LCA(int u,int v){if(dep[u]<dep[v])swap(u,v);for(int i=20;i>=0;i--){if(dep[fa[u][i]]>=dep[v])u=fa[u][i];}if(u==v)return u;for(int i=20;i>=0;i++){if(fa[u][i]!=fa[v][i]){u=fa[u][i];v=fa[v][i];}}return fa[u][0];}LL path_dis(int u,int v){if(!u||!v)return 0;//如果刪除的點(diǎn)是兩邊的其中一邊，在減該點(diǎn)沒有邊的點(diǎn)到它的距離時(shí)，則返回零 //涉及不存在的點(diǎn)時(shí)，返回0； return dis[u]+dis[v]-2*dis[LCA(u,v)];
} 
int main() {ios::sync_with_stdio(0);cin.tie(0);cin>>N>>K;for(int i=1;i<N;++i){int u,v,t; cin>>u>>v>>t;E[u].push_back(v);W[u].push_back(t);E[v].push_back(u);W[v].push_back(t);}	dfs(1,0);LL ans=0;for(int i=1;i<N;i++){cin>>A[i];ans+=path_dis(A[i],A[i-1]);//總長(zhǎng)度 }for(int i=1;i<=k;i++){//減去兩點(diǎn)到該點(diǎn)的距離，加上兩點(diǎn)之間的距離 cout<<ans-path_dis(A[i-1],A[i])-path_dis(A[i],A[i+1])+path_dis(A[i-1],A[i+1])<<' ';}return 0;}

砍樹?

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>e[N],num[N];
int n,m,dep[N],s[N],fa[N][21],ans; void dfs(int u,int Fa){dep[u]=dep[Fa]+1;fa[u][0]=Fa;for(int i=1;i<20;i++){fa[u][i]=fa[fa[u][i-1]][i-1];}for(auto &v:e[u]){//c11if(v==Fa)continue;dfs(v,u);}
}
void dfs2(int u,int Fa){for(int i=0;i<e[u].size();i++){int v=e[u][i],p=num[u][i];if(v==Fa)continue;dfs2(v,u);s[u]+=s[v];//差分 if(s[v]==m)ans==max(ans,p);}
}int LCA(int u,int v){if(dep[u]<dep[v])swap(u,v);   for(int i=20;i>=0;i--){if(dep[fa[u][i]]>=dep[v])u=fa[u][i];}if(u==v)return u;for(int i=20;i>=0;i--){if(fa[u][i]!=fa[v][i]){u=fa[u][i];v=fa[v][i];}	}return fa[u][0];
}int main(){cin>>n>>m;for(int i=1;i<n;i++){int x,y;cin>>x>>y;e[x].push_back(y);num[x].push_back(i);e[y].push_back(x);num[y].push_back(i);}dfs(1,0);for(int i=1;i<=m;i++){int a,b;cin>>a>>b;s[a]++;s[b]++;s[LCA(a,b)]-=2;
//兩點(diǎn)到最近公共祖先那停止，若想斷開兩點(diǎn)，深度需要小于兩點(diǎn)的最近公共祖先	即高于公共祖先的邊，取消掉兩點(diǎn)的差分和}dfs2(1,0);cout<<ans<<endl;return 0;
}