第二篇題解！
可能是退役之前的最后一篇題解了
(好像總共都只寫了兩篇）
不說了，講題：
題面
題意：
有T個資料
有一顆樹（保證所有的的節點都是相連的），有n個節點，每個節點都有相應的權值與序號，現在你要進行M次操作，操作是：
找到權值最大的節點（如果有權值相同且又是最大的節點，則選擇序號較小的節點），與節點直接相連的節點權值+1（本身不增加權值）
最后輸出權值最大的節點（有相同的則輸出序號較小的節點），
資料范圍:
對于 100% 的資料，1≤N≤2×10^6,
1≤M≤10^18,
1≤A i≤2^31-1,
1≤T≤10
部分分就不寫了，
反正很大就是了，看到這個M小于等于10的18次方，你怕了嗎
題解（主要是思路）：
首先看題目，有人看完題面可能會不知道為什么是一棵樹只有你會，題目給出的是N個點，由N-1條雙向路徑相連，
C 國一共有 N 個村莊，N-1 條道路，這些道路都可以雙向通行， 保證小 S 可以從一座村莊到其他任何一座村莊， 這 N 個村莊編號為 1 到 N，
保證小 S 可以從一座村莊到其他任何一座村莊
眾所周知，想要組成環，至少需要與節點數相同的路徑，而題意又保證各個節點一定相連，就必須要N條路徑，但題目給出的只有n-1條路徑
，則是一棵樹，
好啰嗦
看完題意看資料范圍，發現M的范圍巨大，連O（M）的演算法都過不了，不可做，
于是我陷入了思考，先寫一下資料推推規律：
三個點
2 6 3
都相連
2->6->3
M次操作
//1：
num[2]:6最大
3 6 4
//2：
num[2]:6最大
4 6 5
//3：
num[2]:6最大
5 6 6
出現了！相等的點！但是num[2]序號小，答案依舊是選num[2];
//4:
num[2]:6最大
6 6 7
num[3]大于num[2]了；
//5:
num[3]:7最大
6 7 7
又相等了,num[2]序號小，選num[2]，
//6:
num[2]:7最大
7 7 8
num[3]最大了
推到這就差不多了，可以得出以下規律：
（此處的權值指的是初始權值）
x1為權值最大的節點，y1為與它相連的權值相對最大的節點
-
只需要記錄下x1與y1，而其他的節點，拜托，他們超遜的！可以從資料中看出，與6相連的num[1]由于小于num[2]，在答案的選擇中沒有任何競爭力，不與權值最大的節點直接相連的節點就更不要說了，（覺得不對的同學可以自己寫幾組資料試試）
-
在M小于num[2]與num[3]的差時,答案恒為num[2],(num[2]:哼，沒點時間還想超過我？)可以轉化為-----當M小于x1-y1，選x1;
-
然后就是M>=他們的差時：看資料，第3次操作到第6次操作答案是有回圈的，很容易得到是跟M的奇偶性有關的（等于的話就是直接取序號最小就行了），先將M減去x1-y1，奇數取y1,偶數取x1.
這一切都是建立在這個圖是一顆樹的前提下，
代碼實作就行
然后就沒了
嗎？
還有特判！
在代碼實作中，當n=1時的情況要特殊考慮
我就是被這個點坑殺了4個點
85分沒了
結束
不點個贊再走？
有什么意見可以發在評論區哦
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/200879.html
標籤：其他
上一篇：Java多執行緒之CAS
下一篇：Java記憶體泄漏介紹